주벨로퍼의 개발 공부

1. Linked List란?

  연결 리스트는 각 노드가 다른 노드를 가리키는 자료 구조다.

  고정된 크기를 갖는 배열과 달리(물론 자바스크립트에서 배열은 동적 자료 구조이지만 일반적으로 다른 언어에서의 배열을 기준으로 함.)

  연결 리스트는 실행 시간에 메모리를 할당하거나 해제할 수 있는 동적 자료 구조다.

  연결 리스트에는 단일 연결 리스트와 이중 연결 리스트가 있다.

2. Singly Linked List

  단일 연결 리스트는 각 노드가 다음 노드에 대한 참조를 갖는 자료 구조다.

  단일 연결 리스트의 노드에는 data와 next라는 속성이 있고 data에는 노드에 들어갈 값을 저장하고

  next에는 다른 노드에 대한 주소 값을 할당한다. 즉 next를 통해 노드 간의 연결이 이루어진다고 할 수 있다.

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

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

// 연결 리스트의 시작을 head라고 부른다.
// 헤드의 기본적인 디폴트 값은 null이다;

  2 - 1) 데이터의 삽입

    연결 리스트의 헤드가 비어 있다면 헤드가 신규 노드가 된다.

    그렇지 않다면 예전 헤드가 temp에 저장되고 새로운 헤드는 신규로 추가된 노드가 된다.

    마지막으로 새로운 헤드의 next는 예전 헤드를 가리킨다.

class SinglyLinkedList() {
  constructor() {
    this.head = null;
    this.size = 0;
  }
  
  insertNode(value) {
    if (this.head === null) {
      this.head = new Node(value);
    } else {
      let temp = this.head;
      this.head = new Node(value);
      this.head.next = temp;
    }
    this.size++;
  }
}

  2 - 2) 삭제

    노드를 삭제하는 것은 해당 노드의 참조를 제거함으로써 구현할 수 있다.

    삭제는 크게 세 부분으로 나뉜다고 할 수 있다.

    헤드에 있는 노드를 삭제, 중간 노드를 삭제, 마지막 노드를 삭제

    헤드 노드를 삭제하려면 삭제할 항목의 다음 항목이 새로운 헤드가 되면 된다.

    중간 노드를 삭제하려는 경우 해당 노드 이전의 노드가 삭제하려는 노드의 다음 노드를 가리키도록 하면 된다.

    마지막 노드를 삭제하려는 경우 해당 노드의 이전 노드의 next 값을 null로 만든다.

class SinglyLinkedList {



   ...
   
  remove(value) {
    let currNode = this.head;
    if (currNode.data === value) {
      this.head = currNode.next;
      this.size--;
      return;
    } else {
      let prevNode = currNode;
      while (currNode.next) {
        if (currNode.data === value) {
          prevNode.next = currNode.next;
          this.size--;
          return;
        }
        prevNode = currNode;
        currNode = currNode.next;
      }
      prevNode.next = null;
    }
    this.size--;
  }
}

  2 - 3) 검색

    head를 시작으로 반복 순회하면 된다.

class SinglyLinkedList {
  constructor() {
    this.head = null;
    this.size = 0;
  }
  
  
  
  ...
  
  find(value) {
    let currNode = this.head;
    while (currNode.next) {
      if (currNode.data === value) {
        return true;
      }
      currNode = currNode.next;
    }
    return false;
  }
}

3. Doubly Linked List

  이중 연결 리스트는 양방향 단일 연결 리스트이다.

  즉 단일 연결 리스트는 다음 노드만을 참조하지만 이중 연결 리스트는 이전 노드도 참조를 하게된다.

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

class DoublyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }
}

  이중 연결 리스트에서의 데이터의 삽입, 삭제, 검색을 구현하는 것은 단일 연결 리스트와 크게 다르지 않다.

  하지만 삽입과 삭제의 경우 next 속성과 prev 속성 둘 다 갱신돼야 한다.

  3 - 1) 헤드에 항목 삽입하기

class DoublyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }
  
  ...
  
  addAtFront(value) {
    if (this.head === null) {
      this.head = new DoublyLinkedList(value);
      this.tail = this.head;
    } else {
      let temp = new DoublyLinkedList(value);
      temp.next = this.head;
      this.head.prev = temp;
      this.head = temp;
    }
    this.size++;
  }
}

  3 - 2) 테일에 항목 삽입하기

class DoublyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }
  
  ...
  
  addAtTail(value) {
    if (this.tail === null) {
      this.tail = new Node(value);
      this.head = this.tail;
    } else {
      let temp = new Node(value);
      temp.prev = this.tail;
      this.tail.next = temp;
      this.tail = temp;
    }
    this.size++;
  }
}

  3 - 3) 헤드의 항목 삭제

class DoublyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }
  
  ...
  
  deleteAtHead() {
    let toReturn = null;
    if (this.head !== null) {
      toReturn = this.head.data;
      if (this.head === this.tail) {
        this.head = null;
        this.tail = null;
      } else {
        this.head = this.head.next;
        this.head.prev = null;
      }
    }
    this.size--;
    return toReturn;
  }
}

  3 - 4) 테일의 항목 삭제

class DoublyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }
  
  ...
  
  deleteAtTail() {
    let toReturn = null;
    if (this.tail !== null) {
      toReturn = this.tail.data;
      if (this.tail === this.head) {
        this.head = null;
        this.tail = null;
      } else {
        this.tail = this.tail.prev;
        this.tail.next = null;
      }
    }
    this.size--;
    return toReturn;
  }
}

  3 - 5) 검색

class DoublyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }
  
  ...
  
  findAtHead(value) {
    let currNode = this.head;
    while (currNode.next) {
      if (currNode.data === value) {
        return true;
      }
      currNode = currNode.next;
    }
    return false;
  }
  
  findAtTail(value) {
    let currNode = this.tail;
    while (currNode.prev) {
      if (currNode.data === value) {
        return true;
      }
      currNode = currNode.prev;
    }
    return false;
  }
}
  
  

4. 요약

  단일 연결 리스트와 이중 연결 리스트 모두 삽입, 삭제 연산은 O(1) 상수 시간 복잡도를 지닌다.

  하지만 검색은 모두 O(n) 시간이 걸린다.

*참고 : 자바스크립트로 하는 자료 구조와 알고리즘, 지은이: 배세민