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

📌 연결 리스트(Linked List)

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

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

👉 배열과 연결리스트의 차이

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

• 배열은 메모리의 연속된 위치에 저장되고, 연결 리스트는 각 노드가 임의의 위치에 저장된다.
• 또한 배열은 인덱스를 활용하여 특정 원소를 지칭하는 것이 간편하나(O(1)), 연결 리스트는 인덱스가 없다. 그래서 마지막 노드를 찾으려면 첫 노드에서부터 포인터를 통해 다른 노드들을 모두 순차적으로 탐색하며 찾아야 한다.(O(n)).
• 연결 리스트는 노드의 삽입이나 삭제는 그 노드의 앞 뒤 노드에만 영향을 미치므로 배열보다는 비교적 삽입과 삭제가 용이하다 (O(1)). 배열은 요소의 삽입이나 삭제 시, 기존의 모든 요소들이 인덱스를 다시 받아야 하므로 비용이 더 든다.
• 연결 리스트는 앞뒤로 연결이 되었는지 아닌지 여부에 따라 단일(Singly) 연결 리스트와 이중(양방향, Doubly) 연결 리스트가 있다.

📌 단일 연결 리스트 (Singly Linked List)

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

👀 단일 연결 리스트 구현

👉 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);
    // head에 값이 없다면 head와 tail에 새로 생성한 노드를 할당
    if (!this.head) {
      this.head = newNode;
      this.tail = this.head;
      // head에 값이 있다면, tail과 추가된 새 노드를 연결하기 위해 
      // 새로 생성했던 노드를 next pointer에 할당, 
      // 새로 생성했던 노드를 tail에 할당
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }
    // length를 1씩 증가.
    this.length++;

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

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

위 예시를 실행하면 결과는 아래와 같이 나타난다.

👉 pop

pop() {
    // head가 없으면(=연결리스트의 길이가 0이면) undefined를 반환
    if (!this.head) return undefined;
    let current = this.head;
    let newTail = current;
    while (current.next) {
        newTail = current;
        current = current.next;
    }
    // pop된 노드에 대한 꼬리 자르기
    this.tail = newTail;
    this.tail.next = null;
    this.length--;
    if(this.length === 0) {
        this.head = null;
        this.tail = null;
    }
    // pop된 노드 반환
    return current;
}

let list = new SinglyLinkedList();
list.push('HELLO');
list.push('TODAY');
list.push('!');

list.pop()

위 예시를 실행하면 결과는 아래와 같이 나타난다.

👉 shift & unshift

shift() {
    if(this.head) return undefined;
    let currentHead = this.head;
    this.head = currentHead.next;
    this.length--;
    if(this.length === 0) {
        this.tail = null;
    }
    return currentHead;
}
unshift() {
    let newNode = new Node(val);
    if(!this.head) {
        this.head = newNode;
        this.tail = this.head;
    } else {
        newNode.next = this.head;
        this.head = newNode;
    }
    
    this.length++;
    return this;
}

👉 get & set

get(index) {
    if(index < 0 || index >= this.length) return null;
    let counter = 0;
    let current = this.head;
    while(counter !== index) {
        current = current.next;
        counter+=1;
    }
    return current;
}
set(index, val) {
    let foundNode = this.get(index);
    if(foundNode) {
        foundNode.val = val;
        return true;
    }
    return false;
}

👉 insert

insert(index, val) {
    if(index < 0 || index > this.length) return false;
    if(index === this.length) return !!this.push(val);
    if(index === 0) return !!this.unshift(val);
    let newNode = new Node(val)
    let prev = this.get(index-1)
    let temp = prev.next;
    prev.next = newNode;
    newNode.next = temp;
    this.length++;
    return true;
}

👉 remove

remove(index) {
    if (index < 0 || index >= this.length) return undefined;
    if (index === 0) return this.shift();
    if (index === this.length - 1) return this.pop();
    let prev = this.get(index - 1);
    let removed = prev.next;
    prev.next = removed.next;
    this.length--;
    return removed;
}

👉 reverse

reverse() {
    let node = this.head;
    this.head = this.tail;
    this.tail = node;
    let next = null;
    let prev = null;
    for(let i = 0; i < this.length; i++) {
        next = node.next;
        node.next = prev;
        prev = node;
        node = next;
        
    }
    return this;
}

👀 빅오 복잡도

• Insertion - O(1) 단방향 리스트가 배열보다 유리
• Removal - O(1) or O(N) 맨 앞의 요소를 제거하는 경우에는 단방향 리스트가 배열보다 유리하지만 마지막 요소를 제거하는 경우에는 배열이 유리하다
• Searching - O(N) 배열이 단방향 리스트보다 유리
• Access - O(N) 배열이 단방향 리스트보다 유리