[자료구조론] Linked List

연결 리스트 

  배열의 삽입/삭제 연산에서 발생하는 비효율성을 해결하기 위해 등장한 자료구조이다. 논리적,물리적으로 순차적인 배열과 달리, 리스트는 논리적 연결만 순차적이다. 즉, 메모리 주소는 서로 상관관계가 없는 포인터를 가지고 있다. 

연결리스트는 노드들이 연속적으로 연결되어 나타난다.

 단일 연결리스트(Singly Linked List)는 각각의 노드가 다음 노드의 포인터를 가진다. 

 이중 연결리스트(Doubly Linked List)는 각각의 노드가 다음 노드와 이전의 노드의 포인터를 가진다. 

 

메모리 주소는 상관이 없는 대신, 각 원소가 다음 위치에 해당하는 메모리 주소를 포인터(링크) 형태로 가지고 있는다. 따라서 삽입/삭제시에 해당하는 위치 앞 뒤의 원소에 대한 물리적 주소만 변경하면 된다. 

하지만, 연결리스트는 원하는 index를 얻기 위해 처음부터 1을 증가시켜가며 접근해야하는 비효율성이 있다. (O(n))  즉, 배열과 다르게 index 접근에 상수 시간 (O(1))을 가지지 않는다.  ( * 인덱스 접근 -> O(n) / 배열==O(1)  , 삽입 또는 삭제 -> O(1) / 배열 == O(n) ) 

 

    장점: 삽입과 상제가 용이하며 연속된 메모리 공간이 필요 없고 크기 제한이 없다. 

    단점: 구현이 어렵고 까다로우며, 오류가 발생하기 쉽다. 

 

삽입과정

 - 삽입할 노드의 next( 다음 노드의 주소 )를 해당위치의 앞 노드 메모리 주소로 설정하고, 

   해당 위치의 이전 노드의 next를 삽입할 노드의 메모리주소로 설정한다. 

 

삭제과정 

 - 삭제할 노드의 next를 해당 노드의 앞 노드의 메모리 주소로 설정한다. 

 

 

Linked List의 구현 (SLL)

class Node {
    Node next = null; 
    int data;
    
    public Node(int d) {  // d라는 데이터를 가지는 Node
       data = d;
    }
    
    
    void appendToTail(int d) { // d를 끝에 추가하는 함수 
       Node end = new Node(d);
       Node n = this;
       while (n.next != null) {
            n = n.next;
       }
       n.next = end;
    }
}