연결 리스트 (Linked List) / 단일 연결 리스트, 이중 연결 리스트

 

[연결 리스트]

 

---

 

<STUDY>

 

연결 리스트 (Linked List)

데이터를 저장하는 자료 구조

• 순서에 따라 다수의 데이터 저장
• 다음 데이터 요소를 가리키는 인덱스 없이 구성 (객체들이 연속으로 연결)
• 인덱스 X → 직접접근 불가, 연속적으로 접근 가능
• 다수의 노드로 구성 (노드 : 하나의 데이터 요소 저장)
• ⇒ 다음 노드를 가리키는 정보를 저장하고 있어야함 (없는 경우 null)

 

 

# 속성

1. 헤드 (Head) : 시작 노드
2. 테일 (Tail) : 마지막 노드
3. 길이 (Length) : 리스트의 길이

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

 

연결 리스트 vs 배열

연결 리스트	배열
인덱스 X, 헤드 / 테일 존재	인덱스 0
삽입 / 삭제 용이	삽입 / 삭제 복잡함
직접 접근 불가 (연속적으로 접근)	직접 접근 가능 (접근 시간 ↑)

 

단일 연결 리스트 (Singly Linked List)

각 노드가 다음 노드로 오직 단일 방향으로만 연결되어 있는 연결 리스트

• 다음 데이터만을 가리킴 (next)

 

구현

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

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

  pop() {
    if (!this.head) return undefined;

    let cur = this.head;
    let newTail = cur;

    while (cur.next) {
      newTail = cur;
      cur = cur.next;
    }

    this.tail = newTail;
    this.tail.next = null;
    this.length--;

    if (!this.length) {
      this.head = null;
      this.tail = null;
    }
    return cur;
  }

  shift() {
    if (!this.head) return undefined;

    const curHead = this.head;
    this.head = curHead.next;
    this.length--;

    if (!this.length) {
      this.tail = null;
    }

    return curHead;
  }

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

  get(index) {
    if (index < 0 || index >= this.length) return null;

    let current = this.head;
    for (let count = 0; count < index; count++) {
      current = current.next;
    }

    return current;
  }

  set(index, val) {
    let node = this.get(index);
    if (!node) return false;

    node.val = val;

    return true;
  }

  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 prev = this.get(index - 1);
    let newNode = new Node(val);
    newNode.next = prev.next;
    prev.next = newNode;
    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();

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

    return removeNode;
  }

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

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

 

Big O
삽입	O(1)
삭제	O(1) ~ O(n)
탐색	O(n)
접근	O(n)

 

❗스택, 큐 자료 구조를 구현할 수 있다.

 

이중 연결 리스트 (Doubly Linked List)

각 노드가 앞, 뒤로 가는 포인터가 모두 연결되어 있는 연결 리스트

• 단일 연결 리스트에 비해 메모리 사용량이 큼
• 다음 데이터와 이전 데이터를 가리킴 (next, previous)

 

구현

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

  push(val) {
    let newNode = new Node(val);

    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail.next = newNode;
      newNode.prev = this.tail;
      this.tail = newNode;
    }

    this.length++;
    return this;
  }

  pop() {
    if (!this.length) return undefined;

    let prevTail = this.tail;
    if (this.length === 1) {
      this.head = null;
      this.tail = null;
    } else {
      this.tail = prevTail.prev;
      this.tail.next = null;
      prevTail.prev = null;
    }

    this.length--;
    return prevTail;
  }

  shift() {
    if (!this.head) return undefined;

    let prevHead = this.head;
    if (!this.length) {
      this.head = null;
      this.tail = null;
    } else {
      this.head = prevHead.next;
      this.head.prev = null;
      prevHead.next = null;
    }

    this.length--;
    return prevHead;
  }

  unshift(val) {
    let newNode = new Node(val);

    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.head.prev = newNode;
      newNode.next = this.head;
      this.head = newNode;
    }

    this.length++;
    return this;
  }

  get(index) {
    if (index < 0 || index >= this.length) return null;

    if (index > Math.ceil(this.length / 2)) {
      let node = this.tail;
      for (let i = this.length - 1; i > index; i--) {
        node = node.prev;
      }
      return node;
    }

    let node = this.head;
    for (let i = 0; i < index; i++) {
      node = node.next;
    }
    return node;
  }

  set(index, val) {
    let node = this.get(index);
    if (!node) return false;

    node.val = val;
    return true;
  }

  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 prevNode = this.get(index - 1);
    let nextNode = prevNode.next;

    (prevNode.next = newNode), (newNode.prev = prevNode);
    (newNode.next = nextNode), (nextNode.prev = newNode);

    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();

    let removeNode = this.get(index);
    let prevNode = removeNode.prev;
    let nextNode = removeNode.next;

    (prevNode.next = nextNode), (nextNode.prev = prevNode);
    (removeNode.next = null), (removeNode.prev = null);

    this.length--;
    return removeNode;
  }
}

 

Big O
삽입	O(1)
삭제	O(1)
탐색	O(n)
접근	O(n)

 

단일 연결 리스트 vs 이중 연결 리스트

• 이중 연결 리스트가 일정한 상황에서는 더 효율적일 수 있으나 상대적으로 메모리를 많이 소비함

 

단일 연결 리스트	이중 연결 리스트
한 개의 포인터 (next)	두 개의 포인터 (prev, next)
탐색시간 n	탐색시간 n/2
메모리 소모 ↓	메모리 소모 ↑

 

 

---

 

 

 

👉노트 보러가기👈

 

GitHub - ez1n/coding-test: 알고리즘 공부