# 5. 연결 리스트

정의

동적인 자료구조로서 연결리스트는 필요할 때 마다 원소를 추가/삭제할 수 있도 크가 계속 변합니다. 연결 리스트는 인덱스를 유지하는 대신 다른 원소를 가리키는 포인터를 가지고 있습니다.

• 첫 번째 노드 : head
• 마지막 노드 : tail - next pointer는 null을 가르킴

• singly-linked list : 다음 노드를 가리키는 하나의 포인터만 소유
• doubly-linked list : 이전 노드와 다음 노드를 가리키는 두 개의 포인터를 소유

일반적인 배열의 장점은 원소는 대괄호 안에 인덱스만 넣어주면 접근할 수 있어서 사용하기 편리하합니다. 단점은 크기가 고정되어있고 배열의 처음이나 중간에 원소를 생성/삭제할 경우 이 후의 아이템들이 한 칸씩 밀려나야 하기 때문에 선형시간 O(N)이 필요합니다.

연결 리스트의 장점은 원소의 포인터가 향하는 곳을 수정하면서 추가/삭제가 용이하다는 점입니다(O(1)). 또한, 연결리스트는 메모리가 있는 한 넓힐 수 있습니다. 단점은 인덱스로 쉽게 데이터에 접근할 수 있는 배열과 달리 연결 리스트는 원하는 데이터를 찾기 위해 첫 번째부터 포인터를 따라가야 발견할 수 있습니다. 이 때 선형시간으로 전체 길이를 탐색(O(N))해야 합니다.

👉🏻 ES6 관련 연결리스트 아티클

ex. 지하철 구성, 단서 쪽지를 활용한 보물찾기, 손을 잡고 있는 사람들

Singly-linked list

class Node {
  constructor(element, nextPointer = null) {
    this.element = element;
    this.nextPointer = nextPointer;
  }
}

class SinglyLinkedList {
  constructor() {
    this.head = null;
    // 연결의 시작점
    this.size = 0;
    // 리스트 원소의 개수
  }

  append(element) {
    let node = new Node(element);
    // element로 Node 생성
    let current;
    // 리스트의 현재 원소

    if (this.head === null) {
      this.head = node;
      // 리스트가 비어있다면 첫 원소 추가 head가 node를 가리키도록
      // node.nextPointer는 자동으로 null
    } else {
      current = this.head;
      while (current.nextPointer) {
        current = current.nextPointer;
        // 리스트가 원소가 있다면 마지막 원소 발견할 때까지 반복문 실행
        // 리스트의 현재 원소는 current에 담아두고, 
        // current.nextPointer가 null이 되는 지점에서 종료
      }
      current.nextPointer = node;
      // 마지막 원소에 링크할 수 있게 nextPointer에 할당
    }
    this.size++;
    // 리스트 사이즈 업데이트
  }

  insert(index, element) {
    if (index >= 0 && index < this.size) {
      let node = new Node(element);
      let current = this.head;
      let previous;
      let count = 0;

      if (index === 0) {
        // 첫 원소 추가의 경우
        node.nextPointer = current;
        this.head = node;
      } else {
        // 마지막 또는 중간 원소의 경우
        while (count < index) {
          // 리스트를 원하는 index까지 반복문을 수행 : 인덱스의 값을 찾기 위함
          count++;
          // 내부 제어 및 증가를 위한 count
          previous = current;
          // 이전 원소로 현재 인덱스 원소를 할당
          current = current.nextPointer;
          // 현재 인덱스 원소에 포인터가 가르키던 원소 할당
        }
        node.nextPointer = current;
        // 추가한 원소의 포인터를 이전 현재 원소를 가르키게 함
        previous.nextPointer = node;
        // 앞 원소의 포인터를 추가한 원소를 가르키게 함
      }
      this.size++;
      return true;
    } else {
      return false;
    }
  }

  remove(element) {
    let index = this.indexOf(element);
    return this.removeAt(index);
  }

  removeAt(index) {
    if (index >= 0 && index < this.size) {
      // 리스트 크기 사이의 인덱스 값인지 확인
      let current = this.head;
      // 첫 번째 변수 currnet 참조
      let previous;
      let count = 0;

      if (index === 0) {
        // 첫 원소 삭제의 경우
        this.head = current.nextPointer;
        // 포인터 변경으로 삭제
      } else {
        // 마지막 또는 중간 원소의 경우
        while (count < index) {
          // 리스트를 원하는 index까지 반복문을 수행 : 인덱스의 값을 찾기 위함
          count++;
          // 내부 제어 및 증가를 위한 count
          previous = current;
          // 이전 원소로 현재 인덱스 원소를 할당
          current = current.nextPointer;
          // 현재 인덱스 원소에 포인터가 가르키던 원소 할당
        }
        previous.nextPointer = current.nextPointer;
        // 삭제할 원소 앞 원소의 포인터를 삭제할 원소의 포인터로 맞춤
      }
      this.size--;
      // 사이즈 조정
      return current.element;
      // 삭제한 원소 반환
    } else {
      return null;
      // 리스트 크기 사이의 인덱스 값이 아닐 경우 null 리턴
    }
  }

  toString() {
    let current = this.head;
    // head를 시작점으로 기준 삼아 반복문 실행
    let string = '';
    // 결과를 담아둘 변수 초기화

    while (current) {
      string += `${current.element}, `;
      // 순회할 때 current 변수로 원소 존재 여부 파악 
      // 빈 리스트 거나 마지막 원소 다음(null)이면 while 반복문 out
      // 원소 값을 추출해 string에 붙임
      current = current.nextPointer;
      // 다음 원소 순회
    }
    return string;
  }

  indexOf(element) {
    let current = this.head;
    // head 첫 원소로 초기화
    let index = 0;

    while (current) {
      // 원소 순회하며 일치하는 인덱스 탐색
      if (element === current.element) {
        return index;
        // 일치하면 index 반환
      }
      index++;
      current = current.nextPointer;
      // 다르면 인덱스 증가 다음 노드 탐색
    }
    return -1;
    // 발견된 원소가 없으면 -1
  }

  isEmpty() {
    return this.size === 0;
  }

  size() {
    return this.size;
  }

  getHead() {
    return this.head;
  }
  
  print() {
    return console.log(this.toString());
}

let list = new SinglyLinkedList();
list.append(15);
list.append(10);
list.append(13);
list.removeAt(2);
list.insert(1, 16);
list.indexOf(10);
list.remove(16);
list.print();

Doubly-linked list

class Node {
  constructor(element, nextPointer = null, prevPointer = null) {
    this.element = element;
    this.nextPointer = nextPointer;
    this.prevPointer = prevPointer;
  }
}

class DoublyLinkedList {
  constructor() {
    this.head = null;
    // 연결의 시작점
    this.tail = null;
    // 연결의 마지막점
    this.size = 0;
    // 리스트 원소의 개수
  }

  append(element) {
    let node = new Node(element);
    // element로 Node 생성
    let current;
    // 리스트의 현재 원소

    if (this.head === null) {
      this.head = node;
      this.tail = node;
      // 리스트가 비어있다면 첫 원소 추가 head와 tail이 node를 가리키도록
      // node.nextPointer는 자동으로 null
    } else {
      this.tail.nextPointer = node;
      node.prevPointer = this.tail;
      this.tail = node;
      // 마지막 원소의 nextPointer가 새로운 node를 가리키도록
      // 추가되는 node의 prevPointer가 이전 마지막 원소를 가리키도록
      // 가장 마지막 원소로 추가되는 node
    }
    this.size++;
    // 리스트 사이즈 업데이트
  }

  insert(index, element) {
    if (index >= 0 && index < this.size) {
      let node = new Node(element);
      let current = this.head;
      let previous;
      let count = 0;

      if (index === 0) {
        // 첫 원소로 추가의 경우
        if (!this.head) {
          // 리스트 비어 있을 경우 삽입할 node 가르키도록
          this.head = node;
          this.tail = node;
        } else {
          // node를 첫 번 째 원소로 추가
          node.nextPointer = current;
          current.prevPointer = node;
          this.head = node;
        }
      } else if (index === this.size) {
        // 마지막 원소로 추가의 경우
        current = this.tail;
        // 마지막 원소를 current에 담아두고
        current.nextPointer = node;
        // 이전 마지막 원소의 nextPointer를 node를 가르키도록
        node.prevPointer = current;
        // 추가하는 node의 prevPointer를 이전 마지막 원소를 가르키도록
        this.tail = node;
      } else {
        // 중간에 원소로 추가하는 경우
        while (count < index) {
          // 원하는 index에 도달할 때 까지 반복문
          count++;
          previous = current;
          current = current.nextPointer;
        }
        // previous와 current 사이에 원소로 node 끼워 넣기
        node.nextPointer = current;
        previous.nextPointer = node;
        current.prevPointer = node;
        node.prevPointer = previous;
      }
      this.size++;
      return true;
    } else {
      return false;
    }
  }

  remove(element) {
    let index = this.indexOf(element);
    return this.removeAt(index);
  }

  removeAt(index) {
    if (index >= 0 && index < this.size) {
      // 리스트 크기 사이의 인덱스 값인지 확인
      let current = this.head;
      // 첫 번째 변수 currnet 참조
      let previous;
      let count = 0;

      if (index === 0) {
        // 첫 원소 삭제의 경우
        this.head = current.nextPointer;
        // 포인터 변경으로 삭제
        if (this.size === 1) {
          // 리스트의 사이즈 1인 경우 tail 업데이트
          this.tail = null;
        } else {
          // 리스트의 사이즈 1 이상일 경우 head의 prevPointer 업데이트
          this.head.prevPointer = null;
        }
      } else if (index === this.size - 1) {
        // 마지막 원소 삭제의 경우
        current = this.tail;
        this.tail = current.prevPointer;
        this.tail.nextPointer = null;
      } else {
        // 중간 원소의 경우
        while (count < index) {
          // 원하는 index까지 반복문을 수행하여 검색
          count++;
          previous = current;
          current = current.nextPointer;
        }
        previous.nextPointer = current.nextPointer;
        // 삭제할 원소의 앞 원소의 nextPointer를 
        // 삭제할 원소의 nextPointer가 가르키는 곳으로 맞춤
        current.nextPointer.prevPointer = previous;
        // 삭제할 원소의 뒤 원소의 prevPointer를 
        // 삭제할 원소의 앞 원소를 가르키도록
      }

      this.size--;
      // 사이즈 조정
      return current.element;
      // 삭제한 원소 반환
    } else {
      return null;
      // 리스트 크기 사이의 인덱스 값이 아닐 경우 null 리턴
    }
  }

  toString() {
    let current = this.head;
    // head를 시작점으로 기준 삼아 반복문 실행
    let string = '';
    // 결과를 담아둘 변수 초기화

    while (current) {
      string += `${current.element}, `;
      // 순회할 때 current 변수로 원소 존재 여부 파악, 
      // 빈 리스트 거나 마지막 원소 다음(null)이면 while 반복문 out
      // 원소 값을 추출해 string에 붙임
      current = current.nextPointer;
      // 다음 원소 순회
    }
    return string;
  }

  indexOf(element) {
    let current = this.head;
    let index = 0;
    // head 첫 원소로 초기화
    
    if(element === current.element) {
      // 첫 번째 원소 체크
      return 0;
    }
    index++;
    
    while(current.nextPointer) {
      // 중간 원소 체크
      // 원소 순회하며 일치하는 인덱스 탐색
      if(element === current.element) {
        return index;
        // 일치하면 index 반환
      }
      current = current.nextPointer;
      index++;
      // 다르면 인덱스 증가 다음 노드 탐색
    }
    
    if(element === current.element) {
      // 마지막 원소 체크
      return index;
    }
    return -1;
    // 발견된 원소가 없으면 -1
  }

  isEmpty() {
    return this.size === 0;
  }

  size() {
    return this.size;
  }

  getHead() {
    return this.head;
  }
  
  getTail() {
    return this.tail;
  }

  inverseToString() {
    let current = this.tail;
    let string = current ? current.element : '';
    while (current && current.prevPointer) {
      current = current.prevPointer;
      string += ', ' + current.element;
    }
    return string;
  }

  print() {
    return console.log(this.toString());
  }
  
  printInverse(){
    return console.log(this.inverseToString());
  }
}

let list = new DoublyLinkedList();
list.append(15);
list.append(10);
list.append(13);
list.removeAt(2);
list.insert(1, 16);
list.indexOf(10);
list.remove(16);
list.inverseToString();

원형 연결 리스트