단일 연결 리스트란?

• 문자열, 숫자 등 데이터를 저장하는 자료 구조이다.
• 배열은 위치(인덱스)가 있지만 단일 연결 리스트는 요소들마다 위치(인덱스)가 없이 연결되어있다.
• 각각의 요소들을 node 로 정의한다.
• 연결 리스트는 다수의 node들로 구성되고, 각각의node는 데이터와 다음 노드를 가리키는 정보를 저장한다.

속성

HEAD

단일 연결 리스트의 시작 노드를 가리킨다.

TAIL

단일 연결 리스트의 마지막 노드를 가리킨다.

LENGTH

단일 연결 리스트의 전체 길이를 나타낸다.

연결 리스트 구현

Node

각각의 노드를 만들어줄 class를 지정한다.

데이터를 저장하는 val 속성과 다음 노드를 가리키는 next 속성을 추가한다.

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

SinglyLinkedList

각각의 노드들을 연결시키거나, 제거하는 등의 메서드를 정의하는 class 이다.

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

  push(val) {
    const newNode = new Node(val)
    if(!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }
    this.length++;
    return this;
  }

  pop() {
    if(!this.head) return undefined;
    let current = this.head;
    let newTail = current;
    while(current.next) {
      newTail = current;
      current = current.next;
    }
    this.tail = newTail;
    this.tail.next = null;
    this.length--;
    if(this.length === 0) {
      this.head = null;
      this.tail = null;
    }
    return current;
  }

  shift() {
    if(!this.head) return undefined;
    let currentHead = this.head;
    this.head = currentHead.next;
    this.length--;
    if(this.length === 0) {
      this.tail = null;
    }
    return currentHead;
  }

  unshift(val) {
    const newNode = new Node(val);
    if(!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      newNode.next = this.head;
      this.head = newNode;
    }
    this.length++;
    return this;
  }

  get(index) {
    if(index < 0 || index >= this.length) return null;
    else {
      let count = 0;
      let result = this.head;
      while(count !== index) {
        result = result.next;
        count++;
      }
      return result;
    }
  }

  set(index, val) {
    const foundNode = this.get(index);
    if(foundNode) {
      foundNode.val = val;
      return true;
    }
    return false;
  }

  insert(index, val) {
    if(index < 0 || index > this.length) return false;
    if(index === this.length) return !!this.push(val);
    if(index === 0) return !!this.unshift(val);

    const newNode = new Node(val);
    const prev = this.get(index - 1);
    const temp = prev.next;

    prev.next = newNode;
    newNode.next = temp;
    this.length++;
    return true;
  }

  remove(index) {
    if(index < 0 || index >= this.length) return undefined;
    if(index === 0) return this.shift();
    if(index === this.length - 1) return this.pop();
    const previousNode = this.get(index - 1);
    const removed = previousNode.next;
    previousNode.next = removed.next;
    this.length--;
    return removed;
  }

  reverse() {
    let node = this.head;
    this.head = this.tail;
    this.tail = node;

    let next;
    let prev = null;

    for(let i = 0; i < this.length; i++) {
      next = node.next;
      node.next = prev;
      prev = node;
      node = next;
    }

    return this;
  }

  print() {
    const arr = [];
    let current = this.head;
    while(current) {
      arr.push(current.val)
      current = current.next;
    }
    console.log(arr);
  }
}

Big O

Insert - O(1)

배열은 특정 인덱스에 요소를 삽입할 때 다른 요소들의 인덱스 까지 모두 변경되기 때문에 O(n)이다. 따라서 특정 요소를 삽입할 때는 연결 리스트가 유리하다.

Remove - O(n)

리스트에서 특정 요소를 제거하기 위해서는 head 부터 특정 요소의 위치까지 하나 하나 탐색해야한다. 따라서 Remove의 시간 복잡도는 index의 크기에 비례해 증가하기 때문에 O(n) 이다.

Search, Access - O(n)

Remove 와 마찬가지로 특정 요소를 탐색하면 시간 복잡도는 O(n) 이다.
배열의 경우 arr[5] 와 같이 한번에 접근이 가능하기 때문에 O(1) 이다.
따라서 탐색의 경우 연결 리스트 보다 배열이 유리하다.

삽입, 제거 등의 작업에서는 배열보다 연결 리스트가 유리하다.

연결 리스트는 인덱스가 없기 때문에 특정 요소에 접근 할 때는 인덱스가 있는 배열이 더 유리하다.