1. Linked List

추가와 삭제가 반복되는 로직이라면 어떻게 해야될까?

• 배열을 이용하면 시간복잡도가 굉장히 커져 권장되지 않습니다.
• 배열은 탐색이 많을 떄 유용한 자료구조이다.

추가와 삭제가 많을 떄 유용한 자료구조는 연결 리스트이다.

• 연결 리스트는 각 요소를 포인터로 연결하여 관리하는 선형 자료구조다.
• 각 요소는 노드(Node)라고 부르며 데이터 영역과 포인터 영역으로 구성된다.

---

1.1 배열과 차이점

1.1.1 메모리 차이

• 배열은 순차적인 데이터가 들어가기에 메모리 영역을 연속적으로 사용
• 연결 리스트는 순차적이지 않기에 각 데이터가 퍼져있음
  • 퍼져있는 메모리의 영역을 알기 위해 포인터를 사용

1.1.2 배열 요소 추가 및 삭제

1.1.3 연결 리스트 요소 추가 및 삭제

---

2. 연결 리스트(Singly Linked List)

• Head에서 Tail까지 단방향으로 이어지는 연결 리스트
• 가장 단순한 형태인 연결리스트

---

2.1 요소 찾기

‘4’를 찾는다면?

1. HEAD 포인터를 찾는다.
2. HEAD 포인터를 참고하여, 다음 요소인 HEAD를 찾습니다.
3. 그 요소가 찾는 4인지 확인하고, 아니라면 포인터 영역을 통해 다음 요소로 넘어갑니다.
4. 2~3번을 반복

---

2.2 요소 추가

‘3’을 1과 4 데이터 중간에 추가한다면?

1. 3의 포인터 영역을 4를 가르킨다.
2. 2의 포인터 영역을 3을 가르킨다.

---

2.3 요소 삭제

‘2’를 삭제한다면?

1. 삭제할 요소의 이전 포인터 영역을 삭제할 요소의 다음 데이터 영역을 가르키게 한다.
2. 삭제할 요소를 메모리 상에서 지운다.

---

3. 이중 연결 리스트(Doubly Linked List)

• 양방향으로 이어지는 연결 리스트
• 포인터가 2개가 존재
• Singly Linked List보다 자료구조의 크기가 조금 더 크다.

---

3.1 요소 추가

‘3’을 2와 4 중간에 추가한다면?

(1) 추가할 요소의 다음 노드를 4를 가르키게 한다.

(2) 2의 다음 노드를 추가할 요소를 가르키게 한다.

(3) 4의 이전 노드를 추가할 요소를 가르키게 한다.

(4) 추가할 요소의 이전 노드를 2를 가르키게 한다.

---

3.2 요소 삭제

‘2’를 삭제한다면?

(1) 삭제할 요소의 이전 노드를 삭제할 요소의 다음을 가르키게 한다.

(2) 삭제할 요소의 다음의 이전 노드를 삭제할 요소의 이전을 가르키게 한다.

(3) 삭제할 요소를 메모리 상에서 지운다.

---

4. 환형 연결리스트(Circular Linked List)

• Singly 혹은 Doubly Linked List에서 Tail이 Head로 연결되는 연결리스트
• 메모리를 아껴쓸 수 있다.
• 원형 큐 등을 만들때도 사용된다.

---

5. 구현

class Node {
  // 생성자: new 키워드로 객체를 생성할때 자동으로 호출되는 함수
  constructor(value) {
    this.value = value; // 값
    this.next = null; // 포인터
  }
}

class SinglyLinkedList {
  constructor() {
    this.head = null; // head 포인터
    this.tail = null; // tail 포인터
  }

  // 📝 해당하는 값 찾기
  find(value) {
    let currNode = this.head; // 입력받은 연결리스트의 Head 포인터 가져오기
    // 입력한 값을 찾을 때까지 다음 노드로 순회
    while (currNode.value !== value) {
      currNode = currNode.next;
    }
    return currNode; // 값을 찾으면 해당 노드를 반환
  }

  // 📝 끝에 추가
  append(newValue) {
    const newNode = new Node(newValue); // 입력받은 값으로 노드 생성
    // 헤드가 비어있다면
    if (this.head === null) {
      // head와 tail에 생성한 노드를 가리킴
      this.head = newNode;
      this.tail = newNode;
    } else {
      // 값이 존재하면, 다음 노드로 생성한 노드를 가리킴
      // tail은 생성한 노드를 가리킴
      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; // 입력받은 연결리스트의 Head 포인터 가져오기
    // 입력한 값을 찾을 때까지 다음 노드로 순회
    while (prevNode.next.value !== value) {
      prevNode = prevNode.next;
    }
    // 값을 찾고 다음이 null이 아니라면
    if (prevNode.next !== null) {
      // (이전 노드의 다음)을 (다음의 다음)을 가리킴
      // 그러면 중간 노드가 아무 노드를 가리키고 있지 않기 때문에 GC에 의해 메모리 상에서 삭제
      prevNode.next = prevNode.next.next;
    }
  }

  // 📝 출력
  display() {
    let currNode = this.head;
    let displayString = '[';
    while (currNode !== null) {
      displayString += `${currNode.value}, `;
      currNode = currNode.next;
    }
    displayString = displayString.substr(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(); // [1, 2, 3, 5]
console.log(linkedList.find(3));
// Node { value: 3, next: Node { value: 5, next: null } }

linkedList.remove(3);
linkedList.display(); // [1, 2, 5]
linkedList.insert(linkedList.find(2), 10);
linkedList.display(); // [1, 2, 10, 5]

코딩 테스트에서 연결리스트를 직접 구현하는 경우는 많지 않습니다. 배열을 사용하면 되기 때문이죠.