특징

• 메모리가 허용하는 한 요소를 제한없이 추가할 수 있다.
• 탐색은 O(n)이 소요된다.
• 요소를 추가하거나 제거할 때는 O(1)이 소요된다.
• Singly(단일) Linked List, Doubly(이중) Linked List, Circular(원형) Linked List가 존재한다.

연결리스트의 핵심 로직

요소 찾기

요소 추가

요소를 추가하기 위한 탐색을 하게 되면 결국 선형 시간이 소요되므로 주의!

요소 삭제

class Node {
  constructor(value) {
    this.value = value; // data
    this.next = null; // pointer
  }
}

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

  find(value) {
    let currNode = this.head;
    while (currNode.value !== value) {
      currNode = currNode.next;
    }
    return currNode;
  }

  append(newValue) {
    const newNode = new Node(newValue);
    if (this.head === null) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }
  }
  insert(node, newValue) {
    const newNode = new Node(newValue);
    newNode.next = node.next;
    node.next = newNode;
  }

  remove(value) {
    let prevNode = this.head;
    while (prevNode.next.value !== value) {
      prevNode = prevNode.next;
    }
    if (prevNode.next !== null) {
      prevNode.next = prevNode.next.next;
    }
  }

  display() {
    let currNode = this.head;
    let displayString = '[';
    while (currNode !== null) {
      displayString += `${currNode.value}, `;
      currNode = currNode.next;
    }
    displayString = displayString.substring(0, displayString.length - 2);
    displayString += ']';
    console.log(displayString);
  }
}

const linkedList = new SinglyLinkedList();
linkedList.append(1);
linkedList.append(2);
linkedList.append(3);
linkedList.append(5);
linkedList.display();
console.log(linkedList.find(3));
linkedList.remove(3);
linkedList.display();
linkedList.insert(linkedList.find(2), 10);
linkedList.display();

Output

[1, 2, 3, 5]
Node { value: 3, next: Node { value: 5, next: null } }
[1, 2, 5]
[1, 2, 10, 5]

📌 구현하면서 느낀 점

---

처음엔 코드가 많이 복잡해 보였고 눈에 잘 들어오지 않았는데, 노드와 데이터 구조를 그림을 참고하여 한줄한줄 천천히 이해하면서 넘어가니 조금씩 이해가 되었다. 결과적으로 배열을 사용했을 때 보다 Processing 시간을 줄일 수 있어서 다양한 자료구조와 알고리즘을 더욱 공부해야 함을 느꼈다.

📌 앞으로

---

연결 리스트를 숙달하기 위함이 아니라 이러한 과정을 통해서 다음에 배우거나 학습할 자료구조나 알고리즘을 더욱 접근하기 수월하게 하기 위해선 꼭 필요한 과정이라고 생각한다.

📌 참고사이트

wiki

programmers