[자료구조] 단방향 연결리스트

1. 자료구조

자료구조는 스택, 큐, 이진트리, 이진힙, 해시테이블 등 다양한 자료의 구조를 말한다.

자료구조가 많은 이유는 데이터에 따라 특정한 자료구조가 효율적이기 때문이다.

따라서 일부 자료구조는 매우 특화되어있는 반면 배열 객체와 같이 자주 사용되고 있는 

일부 자료구조들은 매우 일반적이다.

 

2. 연결리스트

연결리스트란 데이터 요소들을 가리키는 인덱스 없이 그냥 다수의 데이터 요소들로 구성된다.

마치 객체들이 연속으로 연결되어 있는 기차와 같다고 보면 된다.

여기서 각각의 요소들을 노드라고 부른다.

따라서 연결리스트들은 다수의 노드들로 구성되고 각각의 노드는 문자열 혹은 숫자와 같은 하나의 데이터 요소들을 저장한다.

각 노드들은 다음 노드를 가리키는 정보 역시 저장하고 있어야 하며 다음 노드가 없을경우

아무것도 없음을 의미하는 null을 저장하게 된다.

 

헤드 : 연결리스트의 시작 노드

테일 : 연결리스트의 마지막 노드

중간에 있는 노드들은 일일히 추적하지 않는다.

헤드 노드가 어디있는지만 알고있으며 이 헤드 노드로부터 다음 두번째 노드를 알아내고

두번째 노드에서 세번째 노드를 알아내는 식으로 마지막 노드까지 접근하게 된다.

작업을 용이하게 하기 위해 마지막 연결리스트의 길이를 계속 유지한다.

 

3. 연결리스트 클래스

(1) 클래스 및 노드

class SinglyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }
  // 내부에 메소드들을 작성한다.
}

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

(2) push

연결리스트 끝에 새로운 노드를 추가하는 메소드

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

(3) pop

연결리스트의 마지막 노드를 제거하는 메소드

pop() {
    if (!this.head) return undefined;
    var current = this.head;
    var 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;
  }

(4) shift

연결리스트의 맨앞 노드(head)를 제거하는 메소드

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

(5) unshift

연결리스트의 맨앞 노드(head)를 추가하는 메소드

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

(6) get

해당 인덱스의 노드를 반환하는 메소드

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

(7) set

해당 인덱스 노드의 value값을 바꿔주는 메소드

set(num, val) {
    let setNode = this.get(num);
    if (setNode) {
      setNode.val = val;
      return true;
    }
    return false;
  }

(8) insert

해당 인덱스에 노드를 삽입하는 메소드

insert(index, val) {
    if (index < 0 || index > this.length) return false;
    if (index === 0) return !!this.unshift(val);
    if (index === this.length) return !!this.push(val);
    let newNode = new Node(val);
    let prev = this.get(index - 1);
    let next = prev.next;
    prev.next = newNode;
    newNode.next = next;
    this.length++;
    return true;
  }

(9) remove

해당 인덱스의 노드를 제거하는 메소드

remove(index) {
    if (index < 0 || index >= this.length) return undefined;
    if (index === 0) return this.shift();
    if (index === this.length - 1) return this.pop();

    let prev = this.get(index - 1);
    let removeNode = prev.next;
    prev.next = removeNode.next;
    this.length--;
    return removeNode;
  }

(10) reverse

연결리스트 노드들의 순서를 반대로 뒤집는 메소드

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;
  }

4. 연결리스트 빅O

insertion(삽입)	removal(제거)	searching(탐색)	access(접근)
O(1)	O(1) or O(n)	O(n)	O(n)