단일 연결 리스트 (Singly linked list)

연결 리스트(Linked List)

하나의 개체를 이루는 노드가 연결되어 리스트를 이루는 구조이다. 노드에는 값을 담고 있는 '데이터'와 다음 노드를 가리키는 '링크' 정보를 저장하고 있다. '데이터'에는 숫자, 문자열, 또다른 연결리스트 등 다양한 형식을 가질 수 있다.

리스트의 맨 앞 노드를 헤드(Head), 맨 마지막 노드를 테일(Tail)이라고 한다.

 

배열과 연결리스트의 차이

배열과 연결리스트는 언뜻 비슷해 보이나, 분명한 차이점이 있다.

배열은 메모리의 연속한 위치에 저장되고, 연결 리스트는 각 노드가 임의의 위치에 저장된다.

또한 배열은 인덱스를 활용하여 특정 원소를 지칭하는 것이 간편하나(O(1)), 연결 리스트는 인덱스가 없다. 그래서 마지막 노드를 찾으려면 첫 노드에서부터 포인터를 통해 다른 노드들을 모두 순차적으로 탐색하며 찾아야 한다.(O(n)). 하지만 노드의 삽입이나 삭제는 그 노드의 앞 뒤 노드에만 영향을 미치므로 배열보다는 비교적 삽입과 삭제가 용이하다. 배열은 요소의 삽입이나 삭제 시, 기존의 모든 요소들이 인덱스를 다시 받아야 하므로 비용이 더 든다.

연결 리스트는 앞뒤로 연결이 되었는지 아닌지 여부에 따라 단일(Singly) 연결 리스트와 이중(양방향, Doubly) 연결 리스트가 있다.

 

단일 연결 리스트

데이터들이 한쪽 방향으로만 연결 되어있는 것을 의미한다.

단일 연결 리스트 구현

👉 push

class Node {
  constructor(val) {
    this.val = val;
    this.next = null;
  }
}

class SinglyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }

  push(val) {
    const newNode = new Node(val); // 함수에 전달된 값을 사용하여 새 노드를 생성
    
    if (!this.head) { // head에 값이 없다면 head와 tail에 새로 생성한 노드를 할당
      this.head = newNode;
      this.tail = this.head;
      
    } else {
      // head에 값이 있다면, tail과 추가된 새 노드를 연결하기 위해 
      // 새로 생성했던 노드를 next pointer에 할당, 
      // 새로 생성했던 노드를 tail에 할당
      this.tail.next = newNode;
      this.tail = newNode;
    }
    
    this.length++; // length를 1씩 증가.

    return this; // 이 연결 리스트(this)를 반환.
  }
}

const list = new SinglyLinkedList();
list.push('HELLO');
list.push('TODAY');
list.push('GOODBYE');

결과는 아래와 같이 나타난다.