추가와 삭제가 반복되는 로직에 배열을 사용한다면 시간복잡도가 커지게된다.
배열은 탐색에 유리한 자료 구조이다.

연결 리스트

추가와 삭제가 반복되는 로직에는 연결 리스트를 사용하는 것이 좋다.
연결 리스트는 각 요소들을 포인터로 연결되어있는 선형 자료구조 이다.

특징

• 요소를 동적으로 추가할 수 있다.
• 탐색에 O(n)이 소요된다.
• 요소 추가, 제거시에는 O(1)이 소요된다.

단순 연결 리스트

Head에서 Tail까지 단방향으로 이어지는 연결 리스트

Class Node {
  constructor(value) {
    this.value = value; // 값
    this.next = null; // 포인터
  }
}

Class SingleLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
  }
  // 조회, 추가, 삭제 로직
}

Node는 값과 포인터를 가지며 연결 리스트는 head와 tail을 가진다.

1. 조회

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

위 사진과 같이 head에는 4800이라는 값이 들어가 있으며 이는 값이 10인 노드를 가르킨다.

2-1. 끝 부분에 추가

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
  }
}

받은 값을 통해 새로운 노드를 생성한다. head에 값이 없으면 리스트에 아무런 값이 없다는 뜻이기 때문에 리스트의 head와 tail에 새로 생성한 노드를 부여한다.
만약 값이 존재하면 리스트의 tail의 포인터가 새로운 노드를 가르키도록 구현한다.

2-2. 중간에 추가

insert (node, newValue) {
  const newNode = new Node(newValue);
  newNode.next = node.next;
  node.next = newNode;
}

insert는 노드가 끝이 아닌 중간에 추가되는 로직이다.
insert 파라미터에 있는 node 다음에 새로운 노드를 추가한다.
새로운 값을 받아 새 노드를 생성한 후 생성된 노드의 다음을 입력받은 노드의 다음을 가르키게 만듭니다. 그 후 입력받은 노드의 다음을 새로 생성된 노드를 가르키게 만듭니다.

즉, 기존에 있는 노드를 a,c라고하며 새롭게 추가할 노드를 b라고 가정하자.
기존에는 a의 next가 c의 next를 가르키고 있을 것이다. 이때 b가 중간에 들어오게 된다면 a의 next를 b의 next를 가르키게 만들고 b의 next를 c의 next를 가르키게 되면 중간에 새로운 노드가 추가되는 것이다.

3. 삭제

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

노드가 삭제될 때, O(n) 선형 시간이 소요됩니다. O(1) 상수 시간으로 바꾸고 싶다면 삭제할 노드의 이전 노드를 입력 값으로 넣어주면 된다.
삭제할 노드의 이전 노드를 찾기 위해 prevNode 변수를 생성한다. while문을 돌면서 이전 노드를 찾는다. 그리고 이전 노드의 next 포인터를 삭제할 노드가 아닌 그 다음 노드를 가르키게 되면 삭제하고 싶은 노드를 가르키는 포인터가 없어져 연결 고리가 끊어진다.
삭제된 노드는 가비지 컬렉션을 통해 메모리 상에서 제거된다.

이중 연결 리스트

단순 연결 리스트와 다르게 다음 노드를 가르키는 포인터와 이전 노드를 가르키는 포인터 2개가 존재 한다.

원형 연결 리스트

Tail이 Head로 연결되는 연결 리스트

코딩 테스트

코딩 테스트에서는 연결 리스트와 관련된 문제가 자주 나오지는 않지만 한 번 공부해보자.