[Data-Structure] Linked List (링크드 리스트)

오늘은 링크드 리스트 (Linked List)에 대해서 공부했다.

링크드 리스트 (Linked List)란  각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조이다.(위키백과) 이름에서 말하듯이 데이터를 담고 있는 노드들이 연결되어 있는데, 노드의 포인터가 다음이나 이전의 노드와의 연결을 담당하게 된다.

head 부분은 링크드 리스트의 가장 앞 노드를 뜻하며 tail 부분은 링크드 리스트의 가장 마지막 노드를 뜻한다. (이때, tail의 next Node는 null이다.)

링크드 리스트 그림

 

JS를 이용해서 간단하게 링크드 리스트를 구현해 보았다.

Node 클래스와 LinkedList 클래스를 구현한 뒤, LinkedList의 내장 메서드로 링크드 리스트를 다룰 수 있는 기능을 구현했다.

구현된 기능은 다음과 같다.

• addToTail(value) : 주어진 값을 연결 리스트의 끝에 추가한다.
• remove(value) : 주어진 값을 찾아서 연결을 해제(삭제)한다.
• getNodeAt(index) : 주어진 인덱스의 노드를 찾아서 반환한다. (해당 인덱스에 노드가 없다면 null 반환)
• contains(value) : 연결 리스트에 주어진 값을 가지는 노드의 존재 여부를 반환한다.
• indexOf(value) : 주어진 값의 인덱스를 반환한다. (없을 경우 -1 반환)
• size() : 현재 링크드 리스트의 크기를 반환한다.

 

// Node 클래스 선언
class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

// LinkedList 클래스 선언
class LinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this._size = 0;
  }

  // 주어진 값을 연결 리스트의 끝에 추가
  addToTail(value) {
    let node = new Node(); // node 추가

    node.value = value; // 값 넣기
    if (this.head === null) { // 첫 노드 값이 비어 있을 때
      this.head = node; // 첫 노드와 마지막 노드를 현재 노드로 지정
      this.tail = node;
    } else {
      this.tail.next = node; // 마지막 노드의 다음 값을 현재 노드값으로 지정
      this.tail = node; // 마지막 노드를 현재 노드로 지정
      node.next = null; // 마지막 노드의 다음 노드를 null로 지정
    }

    this._size = this._size + 1; // size 추가
  }

  // 주어진 값을 찾아서 연결을 해제(삭제)
  remove(value) {
    let temp = this.head; // 현재 노드
    let beforeNode = temp; // 현재 노드의 이전 노드

    if (this.head.value === value) { // head에서 주어진 값을 찾았을 경우 
      this.head = this.head.next; // 첫 노드의 연결을 해제하고 첫 노드를 다음 노드로 지정
      this._size = this._size - 1; // 사이즈 감소
      return;
    }

    while (temp !== null && temp.value !== value) { // temp가 null이면 마지막 노드의 다음 노드이며 value값이 같을 때 빠져나가기 위해
      beforeNode = temp; // 다음 루프의 이전노드는 현재 노드
      temp = temp.next; // value값과 같지 않을 때 temp에 다음 노드 저장  
    }

    // 만약 못찾았을때
    if (temp === null) {
      return;
    }

    beforeNode.next = temp.next; // 전 노드 값의 다음 값을 변경
    //temp.next = null; // temp의 다음 값 지우기
    this._size = this._size - 1;
  }

  // 주어진 인덱스의 노드를 찾아서 반환. 
  // 값이 아니라 노드를 반환해야 하는 것에 주의. 해당 인덱스에 노드가 없다면 undefined를 반환.
  getNodeAt(index) {
    let temp = this.head; // 현재 노드
    if (index === 1) { // 주어진 index가 1일때 루프를 돌지 않고 리턴하기 위해
      return temp.next;
    }
    if (index >= this._size) { // 주어진 index가 현재 링크드 리스트의 크기보다 크다면
      return undefined;
    }
    for (let i = 0; i < index - 1; i++) { // 인덱스의 수만큼 다음 노드로 넘겨줌
      temp = temp.next;
    }

    return temp;
  }

  // 연결리스트에 주어진 값을 가지는 노드의 존재 여부를 반환합니다.
  contains(value) {
    let temp = this.head; // 현재 노드
    let beforeNode = this.head; // 현재 노드의 이전 노드

    if (this.head.value === value) { // 첫 노드에서 값을 찾았을 때 (루프 돌기 전에 리턴시키기 위해)
      return true;
    }

    // remove로직과 비슷
    while (temp !== null && temp.value !== value) {
      beforeNode = temp;
      temp = temp.next;
    }

    // 만약 못찾았을때
    if (temp === null) {
      return false;
    }
    // 찾았을 때
    return true;

  }

  // 주어진 값의 인덱스를 반환합니다. 없을 경우 -1을 반환합니다.
  indexOf(value) {
    let temp = this.head; // 현재 노드
    let index = 0; // 반환할 인덱스

    if (this.head.value === value) { // 첫 노드에서 값을 찾았을 때
      return 0;
    }

    // remove로직과 비슷
    while (temp !== null && temp.value !== value) {
      temp = temp.next;
      index++; // 찾지 못했을 때 index 추가
    }

    // 만약 못찾았을때
    if (temp === null) {
      return -1;
    }
    return index;
  }

  // 현재 링크드 리스트의 크기를 반환
  size() {
    return this._size;
  }
}



module.exports = LinkedList;

 

간단한 사용예시를 보자면

let linkedList = new LinkedList();

linkedList.addToTail(1);
linkedList.addToTail(2);
linkedList.addToTail(3);

console.log(linkedList.contains(2)); // true
linkedList.remove(2);
console.log(linkedList.contains(2)); // false

console.log(linkedList.size()); // 2

 

이렇게 링크드 리스트 (LinkedList)를 알아보았다.