[자료구조] 연결리스트 (Linked List)

1. 무엇인가
   • 일반 명사 : 연결된 목록?
   • 고유 명사 : 메모리 공간에서 떨어져 저장되어 있는 데이터들를 포인터로 연결해서 리스트 형태로 구현한 자료구조
2. 왜 사용하는가?
   배열의 단점(크기 예측의 어려움, 삭제/삽입의 비효율성)을 해결하기 위해서 사용되는 자료구조이다.
   - 연결 리스트 만들 때는 필요한 데이터만큼 노드를 생성하고, 생성된 노드를 연결하는 방식으로 만들기 때문에 데이터의 전체 크기를 고려하지 않아도 된다.
   - 데이터의 수정, 삽입 시에는 노드를 만들거나 삭제한 후, 관련된 노드가 가리키는 포인터만 변경하기 때문에 배열에 비해 간단하다.
   
   
3. 배열과 연결리스트의 비교
   - 데이터의 크기가 변하지 않고, 참조가 자주 일어난다면 배열을 사용.
   - 데이터의 크기가 자주 변하고, 수정, 삭제가 많이 일어날 경우 연결리스트를 사용.
   
   
4. 장단점
   
   1. 장점
      - 생성 시, 빈 메모리 공간 아무곳에 데이터를 생성하고 연결만 해주면 되기 때문에, 초기 크기를 알 필요가 없다.
      - 데이터를 삽입, 삭제할 경우, 다음 포인터만 수정하면 되기 때문에 간단하다.
   2. 단점
      - 데이터 참조 시, 시작 노드부터 접근하여, 필요한 데이터까지 순차적으로 접근해야 한다. (O(n)의 성능을 가진다.)
         (반면, 배열의 경우, 인덱스를 알면, 원하는 데이터를 한번에 참조할 수 있다. (O(1)의 성능을 가진다.))
      
5. 어떻게 사용하는가
   
   • 연결리스트의 추상 자료형
     - printAll() - 모든 데이터 출력
     - clear() - 모든 데이터 제거
     - insertAt(index, data) - 인덱스 삽입
     - insertLast(data) - 마지막 삽입
     - deleteAt(index) - 인덱스 제거
     - deleteLast() - 마지막 제거
     - getNodeAt() - 인덱스 읽기
   • 자바스크립트 코드로 연결리스트 만들어보기

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

class LinkedList{
  constructor(){
    this.head = null;
    this.count = 0;
  }

  printAll(){
    let text = '['
    let currentNode = this.head;
    for(let i = 0; i < this.count; i++) {
      text += currentNode.data;
      currentNode = currentNode.next;
      if (currentNode != null) {
        text += ',';
      } else {
        text += ']';
      }
    }
    console.log(text);
  }

  clear(){
    this.head = null;
    this.count = 0;
  }

  insertAt(index, data){
    if(index > this.count || index < 0) {
      throw new Error('범위를 넘어갔습니다.');
    }

    let newNode = new Node(data);

    if(index === 0) {
      newNode.next = this.head;
      this.head = newNode;
    } else {
      let currentNode = this.head;
      for (let i = 0; i < index - 1; i++) {
        currentNode = currentNode.next;
      }
      newNode.next = currentNode.next;
      currentNode.next = newNode;
    }
    this.count++;
  }

  insertLast(data) {
    this.insertAt(this.count, data);
  }

  deleteAt(index) {
    if(index > this.count || index < 0) {
      throw new Error('제거할 수 없습니다.');
    }
    let currentNode = this.head;

    if (index === 0) {
      let deletedNode = this.head;
      this.head = deletedNode.next;
      this.count--;
      return deletedNode;
    } else {
      for(let i = 0; i < index - 1; i++) {
        currentNode = currentNode.next;
      }
      const deletedNode = currentNode.next;
      currentNode.next = deletedNode.next;
      this.count--;
      return deletedNode;
    }
  }

  deleteLast() {
    this.deleteAt(this.count - 1);
  }

  getNodeAt(index) {
    if(index > this.count || index < 0) {
      throw new Error('범위를 초과했습니다.');
    }

    let currentNode = this.head;
    for(let i = 0; i < index; i++) {
      currentNode = currentNode.next;
    }

    return currentNode;
  }
}

export {Node, LinkedList};

참조한 글들
- https://bigbigpark.github.io/data_structure/linkedlist/
- https://hyeinisfree.tistory.com/64
- https://terms.naver.com/entry.naver?docId=3597406&cid=58598&categoryId=59316
- https://terms.naver.com/entry.naver?docId=2270421&cid=51173&categoryId=51173