Data Structure 공부 중 이해한 부분을 정리합니다. 각 자료구조의 구현은 JavaScript를 이용하였습니다.

Linked List

연결리스트는 그 크기가 동적인 자료구조로, 노드의 연결로 이루어진 자료구조 입니다.

Linked List 가져오기, 추가, 삭제

연결리스트는 어떠한 임의의 지점에 데이터의 추가와 삭제를 할 경우, O(1)의 시간복잡도를 가집니다. 추가와 삭제에 대해 O(n)의 시간복잡도를 갖는 배열과는 다릅니다.

그러나 연결리스트의 각 노드는 인덱스를 갖지 않습니다. 그래서 특정데이터를 검색할 경우 처음부터 전체 리스트를 훑어야 하며, 이는 O(n)의 시간복잡도를 가집니다.

Linked List의 종류

단일 연결리스트와, 이중 연결리스트 등이 있습니다.

• 단일연결리스트는 각 노드가 다음노드를 참조하고 있는 링크를 갖습니다(단방향).
• 이중 연결리스트는 각 노드가 이전 노드와 다음노드를 참조하는 링크를 가지고 있습니다(양방향).

Linked List 구현 💻

이 구현에서는 단일 연결리스트를 구현 하였습니다

구현한 메소드

• addToTail(value) - 주어진 값을 연결 리스트의 끝에 추가합니다.
• remove(value) - 주어진 값을 찾아서 연결을 해제(삭제)합니다
• getNodeAt(index) - 주어진 인덱스의 노드를 찾아서 반환합니다. 값이 아니라 노드를 반환해야 하는 것에 주의하세요. 해당 인덱스에 노드가 없다면 undefined를 반환합니다.
• contains(value) - 연결리스트에 주어진 값을 가지는 노드의 존재 여부를 반환합니다.
• indexOf(value) - 주어진 값의 인덱스를 반환합니다. 없을 경우 -1을 반환합니다.

Pesuedo Code

• addToTail(value) - this.head가 존재하면 this.tail.next에 value를 값으로 갖는 노드를 연결시킵니다. this.head가 존재하지 않는다면 노드를 head와 tail에 동시에 추가합니다.

• remove(value) - 연결리스트에서의 삭제는 연결을 해제하는 것을 의미합니다. head부터 값을 조사해서 계속해서 next를 조사합니다. 일치하는 값이 나온다면 이전 노드의 next를 일치하는 노드의 다음 노드로 연결시킵니다. 만약 찾는 노드가 head라면 다음 노드를 head로, 찾는 노드가 마지막이라면 이전 노드를 tail로 변경 시켜야합니다.

• getNodeAt(index) - count를 선언합니다. 역시 head부터 조사하여 count를 증가시키는데 이가 index와 같아지면 해당 노드를 return 시킵니다.

• contains(value) - head부터 next를 조사하면서 노드의 value가 전달인자와 일치하면 true를 return하고 tail까지 조사했는데 일치하는 값이 없다면 false를 return 합니다.

• indexOf(value) - index를 선언하고 역시 head부터 조사하면서 일치할 때까지 index를 +1합니다. 일치하면 해당 인덱스를 return하고 tail까지 조사했는데 일치하는 값이 없다면 -1을 return 합니다.

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

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

  addToTail(value) {
    let node = new Node(value);
    if(this.head){
      this.tail.next = node;
      this.tail = node;
      this._size++;
    } else{
      this.head = node;
      this.tail = node;
      this._size++;
    }

    return node;
   
  }

  remove(value) {
    let curNode = this.head; 
    let prevNode;

    while(curNode){
      if(curNode.value === value){
        if(!prevNode) this.head = curNode.next;
        else if(curNode === this.tail){
          prevNode.next = null;
          this.tail = prevNode;
        } else {
          prevNode.next = curNode.next;
        }
        this._size--;
      }
      prevNode = curNode;
      curNode = curNode.next;
    }
  }

  getNodeAt(index) {
    let count = 0;
    let currentnode = this.head;

    while(currentnode) {
      if(count === index) {
        return currentnode;
      }
      currentnode = currentnode.next;
      count++;
    }
    return undefined;
    
  }

  contains(value) {
    let curNode = this.head;
    while(curNode){
      if(curNode.value === value) return true;
      curNode = curNode.next
    }
    return false;
  }

  indexOf(value) {
    let index = 0;
    let curNode = this.head;

    while(curNode){
      if(curNode.value === value) return index;
      curNode = curNode.next;
      index++;
    }

    return -1;
  }

  size() {
    return this._size;
  }
}