연결 리스트

• 연결 리스트는 일련의 원소를 배열처럼 순차적으로 저장하지만, 원소들이 메모리상에 연속적으로 위치하지 않는 자료구조이다. 즉, 논리적인 순서는 지켜지지만 물리적인 순서는 상관하지 않는다.
• data와 address 정보를 가지는 노드들이 연결된 형태이며 address에는 다음 연결된 노드의 주소가 담겨있다.
• 연결 리스트의 종류에는 구현 방법에 따라 단순 연결 리스트, 이중 연결 리스트, 원형 연결 리스트 등이 있다.
  
  
  

※ 시간복잡도 비교

• 연결 리스트는 데이터의 삽입 및 삭제의 경우 배열 보다 유리하다.
  - 배열에서의 데이터 공간을 늘리거나 줄이지 않아도 되기 때문이다.
  
  
• 연결 리스트는 데이터의 탐색의 경우는 배열 보다 불리하다.
  - 배열은 인덱스를 통한 임의접근이 가능하지만 연결 리스트의 경우 특정 원소를 처음부터 찾아야 하기 때문이다.
  
  
• 위의 경우는 탐색과, 삽입 및 삭제의 경우에만 해당하는 시간복잡도이며 전체적인 구현에서의 시간 복잡도는 상황마다 상이하므로 아래의 구현 코드를 보며 이해해보자.

1. 단순 연결 리스트

구현 - javaScript

'use strict';

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

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

  // 리스트의 데이터 탐색 : O(n)
  find(idx) {
    let curNode = this.head;
    let count = 0;

    while (count !== idx) {
      curNode = curNode.link;
      count++;
    }

    if (!curNode) {
      console.log('해당 위치의 데이터가 존재 하지 않습니다.\n');
      return;
    }

    return curNode;
  }

  // 리스트의 맨 끝에 데이터 삽입 : 탐색 O(1) + 삽입 O(1) => O(1)
  append(value) {
    const newNode = new Node(value);

    if (this.isEmpty()) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail.link = newNode;
      this.tail = newNode;
    }

    this.length++;

    return;
  }

  // 리스트의 맨 끝 데이터 삭제 : 탐색 O(n) + 삭제 O(1) => O(n)
  removeLast() {
    const removeNode = this.tail;

    if (this.isEmpty()) {
      console.log('이미 데이터가 존재 하지 않습니다.');

      return;
    }

    if (this.length === 1) {
      this.head = null;
      this.tail = null;

      this.length--;

      return removeNode.data;
    }

    let curNode = this.head;
    while (curNode.link !== this.tail) {
      curNode = curNode.link;
    }

    curNode.link = null;
    this.tail = curNode;

    this.length--;

    return removeNode.data;
  }

  // 리스트의 맨 앞에 데이터 삽입 : 탐색 O(1) + 삽입 O(1) => O(1)
  prepend(value) {
    const newNode = new Node(value);

    if (this.isEmpty()) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      const temp = this.head;

      this.head = newNode;
      this.head.link = temp;
    }

    this.length++;

    return;
  }

  // 리스트의 맨 앞 데이터 삭제 : 탐색 O(1) + 삭제 O(1) => O(1)
  removeFirst() {
    const removeNode = this.head;

    if (this.isEmpty()) {
      console.log('이미 데이터가 존재하지 않습니다.');

      return;
    }

    if (this.length === 1) {
      this.head = null;
      this.tail = null;
    } else {
      this.head = removeNode.link;
    }

    this.length--;

    return removeNode;
  }

  // 맨 앞과 뒤를 제외한 임의의 위치에 데이터 삽입 : 탐색 O(n) + 삽입 O(1) => O(n)
  insert(idx, value) {
    if (idx >= this.length) {
      // 리스트에 존재하지 않은 인덱스 이다.
      // 그러므로 리스트의 맨 뒤에 삽입, append 시간복잡도 반영

      console.log(
        '리스트에 존재하지 않는 인덱스이므로 리스트의 마지막에 데이터를 삽입하겠습니다.'
      );
      return this.append(value);
    } else if (idx === 0) {
      // 리스트의 맨 앞에 삽입, prepend 시간복잡도 반영
      return this.prepend(value);
    }

    const newNode = new Node(value);
    const prevNode = this.find(idx - 1);

    newNode.link = prevNode.link;
    prevNode.link = newNode;

    this.length++;

    return;
  }

  // 맨 앞과 뒤를 제외한 임의의 위치에 데이터 삭제 : 탐색 O(n) + 삭제 O(1) => O(n)
  remove(idx) {
    if (idx >= this.length) {
      // 리스트에 존재하지 않은 인덱스 이다.
      console.log('리스트에 존재하지 않는 인덱스입니다.');

      return;
    } else if (idx === 0) {
      // 리스트의 맨 앞 데이터 삭제이므로, removeFirst 시간복잡도 반영
      return this.removeFirst();
    } else if (idx === this.length - 1) {
      // 리스트의 맨 뒤 데이터 삭제이므로, removeLast 시간복잡도 반영
      return this.removeLast();
    }

    const prevNode = this.find(idx - 1);
    const removeNode = prevNode.link;

    prevNode.link = removeNode.link;

    this.length--;

    return removeNode;
  }

  // 리스트의 데이터 포함 여부
  isEmpty() {
    return this.length === 0 ? true : false;
  }

  // 리스트의 요소들을 보기 쉽게 프린트
  printList() {
    let cur = this.head;
    let str = '';

    while (cur) {
      str += cur.data + ' ';
      cur = cur.link;
    }

    if (str.length === 0) {
      console.log('데이터가 존재하지 않습니다.\n');
    } else {
      console.log(`List Size : ${this.size()} \n${str} \n`);
    }

    return;
  }

  size() {
    return this.length;
  }
}

const singlyLinkedList = new SinglyLinkedList();

singlyLinkedList.append(1);
singlyLinkedList.printList();

singlyLinkedList.append(2);
singlyLinkedList.printList();

singlyLinkedList.removeLast();
singlyLinkedList.printList();

singlyLinkedList.removeLast();
singlyLinkedList.printList();

singlyLinkedList.prepend(1);
singlyLinkedList.printList();

singlyLinkedList.prepend(2);
singlyLinkedList.printList();

singlyLinkedList.removeFirst();
singlyLinkedList.printList();

singlyLinkedList.insert(1, 2);
singlyLinkedList.printList();

singlyLinkedList.insert(1, 3);
singlyLinkedList.printList();

singlyLinkedList.remove(1);
singlyLinkedList.printList();

• 결과
  

2. 이중 연결 리스트

• 단순 연결 리스트는 한 방향으로만 연결되어 있어 특정 노드의 전 노드를 알려면 전체 탐색이 필요하다.
• 위와 같은 경우를 보완하여 양쪽 방향 모두의 노드를 연결한 리스트가 이중 연결 리스트이다.
• 이전 노드의 주소, 데이터, 다음 노드의 주소를 가지므로 단일 연결리스트에 비해 메모리를 2배 만큼 더 사용하게 된다.
• 이중 연결 리스트의 경우 removeLast() 메소드의 시간 복잡도가 단일 연결 리스트에서의 O(n)에서 O(1)으로 개선되었다. 아래의 코드를 자세히 살펴보자.
  
  

구현 - javaScript

'use strict';

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

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

  // 리스트의 데이터 탐색 : O(n)
  find(idx) {
    let curNode = this.head;
    let count = 0;

    while (count !== idx) {
      curNode = curNode.next;
      count++;
    }

    if (!curNode) {
      console.log('해당 위치에 데이터가 존재하지 않습니다.');
      return;
    }

    return curNode;
  }

  // 리스트의 맨 끝에 데이터 삽입 : 탐색 O(1) + 삽입 O(1) => O(1)
  append(value) {
    const newNode = new Node(value);

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

    this.length++;

    return;
  }

  // 리스트의 맨 끝 데이터 삭제 : 탐색 O(1) + 삭제 O(1) => O(1)
  removeLast() {
    const removeNode = this.tail;

    if (this.isEmpty()) {
      console.log('이미 데이터가 존재하지 않습니다.\n');

      return;
    }

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

    this.length--;

    return removeNode;
  }

  // 리스트의 맨 앞에 데이터 삽입 : 탐색 O(1) + 삽입 O(1) => O(1)
  prepend(value) {
    const newNode = new Node(value);

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

    this.length++;

    return;
  }

  // 리스트의 맨 앞 데이터 삭제 : 탐색 O(1) + 삭제 O(1) => O(1)
  removeFirst() {
    const removeNode = this.head;

    if (this.isEmpty()) {
      console.log('이미 데이터가 존재하지 않습니다.\n');

      return;
    }

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

    this.length--;

    return removeNode;
  }

  // 맨 앞과 뒤를 제외한 임의의 위치에 데이터 삽입 : 탐색 O(n) + 삽입 O(1) => O(n)
  insert(idx, value) {
    if (idx >= this.length) {
      // 리스트에 존재하지 않은 인덱스 이다.
      // 그러므로 리스트의 맨 뒤에 삽입, append 시간복잡도 반영

      console.log(
        '리스트에 존재하지 않는 인덱스이므로 리스트의 마지막에 데이터를 삽입하겠습니다.'
      );
      return this.append(value);
    } else if (idx === 0) {
      // 리스트의 맨 앞에 삽입, prepend 시간복잡도 반영
      return this.prepend(value);
    }

    const newNode = new Node(value);
    const prevNode = this.find(idx - 1);

    prevNode.next.prev = newNode;
    newNode.next = prevNode.next;
    prevNode.next = newNode;
    newNode.prev = prevNode;

    this.length++;

    return;
  }

  // 맨 앞과 뒤를 제외한 임의의 위치에 데이터 삭제 : 탐색 O(n) + 삭제 O(1) => O(n)
  remove(idx) {
    if (idx >= this.length) {
      // 리스트에 존재하지 않은 인덱스 이다.
      console.log('리스트에 존재하지 않는 인덱스입니다.');

      return;
    } else if (idx === 0) {
      // 리스트의 맨 앞 데이터 삭제이므로, removeFirst 시간복잡도 반영
      return this.removeFirst();
    } else if (idx === this.length - 1) {
      // 리스트의 맨 뒤 데이터 삭제이므로, removeLast 시간복잡도 반영
      return this.removeLast();
    }

    const removeNode = this.find(idx);
    const prevNode = removeNode.prev;

    prevNode.next = removeNode.next;
    removeNode.next.prev = prevNode;

    this.length--;

    return removeNode;
  }

  // 리스트의 데이터 포함 여부
  isEmpty() {
    return this.length === 0 ? true : false;
  }

  // 리스트의 요소들을 보기 쉽게 프린트
  printList() {
    let curNode = this.head;
    let str = '';

    while (curNode) {
      str += curNode.data + ' ';
      curNode = curNode.next;
    }

    if (str.length === 0) {
      console.log('데이터가 존재하지 않습니다.\n');
    } else {
      console.log(`List Size : ${this.size()} \n${str} \n`);
    }

    return;
  }

  size() {
    return this.length;
  }
}

const doublyLinkedList = new DoublyLinkedList();

doublyLinkedList.append(1);
doublyLinkedList.printList();

doublyLinkedList.append(2);
doublyLinkedList.printList();

doublyLinkedList.removeLast();
doublyLinkedList.printList();

doublyLinkedList.removeLast();
doublyLinkedList.printList();

doublyLinkedList.prepend(1);
doublyLinkedList.printList();

doublyLinkedList.prepend(2);
doublyLinkedList.printList();

doublyLinkedList.removeFirst();
doublyLinkedList.printList();

doublyLinkedList.insert(1, 2);
doublyLinkedList.printList();

doublyLinkedList.insert(1, 3);
doublyLinkedList.printList();

doublyLinkedList.remove(1);
doublyLinkedList.printList();

console.log(doublyLinkedList);

• 결과
  

3. 원형 연결 리스트

• 단순 연결 리스트나 이중 연결 리스트에서 tail이 head로 연결되는 연결리스트이다.

'use strict';

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

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

  // 리스트의 데이터 탐색 : O(n)
  find(idx) {
    let curNode = this.head;
    let count = 0;

    while (count !== idx) {
      if(curNode.next === this.head) break;

      curNode = curNode.next;
      count++;
    }

    if (!curNode) {
      console.log('해당 위치에 데이터가 존재하지 않습니다.');
      return;
    }

    return curNode;
  }

  // 리스트의 맨 끝에 데이터 삽입 : 탐색 O(1) + 삽입 O(1) => O(1)
  append(value) {
    const newNode = new Node(value);

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

      this.head.prev = newNode;
      this.tail = newNode;

    }

    this.length++;

    return;
  }

  // 리스트의 맨 끝 데이터 삭제 : 탐색 O(1) + 삭제 O(1) => O(1)
  removeLast() {
    const removeNode = this.tail;

    if (this.isEmpty()) {
      console.log('이미 데이터가 존재하지 않습니다.\n');

      return;
    }

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

    this.length--;

    return removeNode;
  }

  // 리스트의 맨 앞에 데이터 삽입 : 탐색 O(1) + 삽입 O(1) => O(1)
  prepend(value) {
    const newNode = new Node(value);

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

      this.head = newNode;
      this.head.prev = this.tail;
      this.tail.next = this.head;
    }

    this.length++;

    return;
  }

  // 리스트의 맨 앞 데이터 삭제 : 탐색 O(1) + 삭제 O(1) => O(1)
  removeFirst() {
    const removeNode = this.head;

    if (this.isEmpty()) {
      console.log('이미 데이터가 존재하지 않습니다.\n');

      return;
    }

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

    this.length--;

    return removeNode;
  }

  // 맨 앞과 뒤를 제외한 임의의 위치에 데이터 삽입 : 탐색 O(n) + 삽입 O(1) => O(n)
  insert(idx, value) {
    if (idx >= this.length) {
      // 리스트에 존재하지 않은 인덱스 이다.
      // 그러므로 리스트의 맨 뒤에 삽입, append 시간복잡도 반영

      console.log(
        '리스트에 존재하지 않는 인덱스이므로 리스트의 마지막에 데이터를 삽입하겠습니다.'
      );
      return this.append(value);
    } else if (idx === 0) {
      // 리스트의 맨 앞에 삽입, prepend 시간복잡도 반영
      return this.prepend(value);
    }

    const newNode = new Node(value);
    const prevNode = this.find(idx - 1);

    prevNode.next.prev = newNode;
    newNode.next = prevNode.next;
    prevNode.next = newNode;
    newNode.prev = prevNode;

    this.length++;

    return;
  }

  // 맨 앞과 뒤를 제외한 임의의 위치에 데이터 삭제 : 탐색 O(n) + 삭제 O(1) => O(n)
  remove(idx) {
    if (idx >= this.length) {
      // 리스트에 존재하지 않은 인덱스 이다.
      console.log('리스트에 존재하지 않는 인덱스입니다.');

      return;
    } else if (idx === 0) {
      // 리스트의 맨 앞 데이터 삭제이므로, removeFirst 시간복잡도 반영
      return this.removeFirst();
    } else if (idx === this.length - 1) {
      // 리스트의 맨 뒤 데이터 삭제이므로, removeLast 시간복잡도 반영
      return this.removeLast();
    }

    const removeNode = this.find(idx);
    const prevNode = removeNode.prev;

    prevNode.next = removeNode.next;
    removeNode.next.prev = prevNode;

    this.length--;

    return removeNode;
  }

  // 리스트의 데이터 포함 여부
  isEmpty() {
    return this.length === 0 ? true : false;
  }

  // 리스트의 요소들을 보기 쉽게 프린트
  printList() {
    let curNode = this.head;
    let str = '';

    while (curNode) {
      
      str += curNode.data + ' ';
      curNode = curNode.next;

      if(curNode === this.head) break;

    }

    if (str.length === 0) {
      console.log('데이터가 존재하지 않습니다.\n');
    } else {
      console.log(`List Size : ${this.size()} \n${str} \n`);
    }

    return;
  }

  size() {
    return this.length;
  }
}

const circularLinkedList = new CircularLinkedList();

circularLinkedList.append(1);
circularLinkedList.printList();

circularLinkedList.append(2);
circularLinkedList.printList();

circularLinkedList.append(3);
circularLinkedList.printList();

circularLinkedList.removeLast();
circularLinkedList.printList();

circularLinkedList.removeLast();
circularLinkedList.printList();

circularLinkedList.removeLast();
circularLinkedList.printList();

circularLinkedList.prepend(1);
circularLinkedList.printList();

circularLinkedList.prepend(2);
circularLinkedList.printList();

circularLinkedList.prepend(3);
circularLinkedList.printList();

circularLinkedList.removeFirst();
circularLinkedList.printList();

circularLinkedList.removeFirst();
circularLinkedList.printList();


circularLinkedList.insert(1, 2);
circularLinkedList.printList();

circularLinkedList.insert(1, 3);
circularLinkedList.printList();

circularLinkedList.remove(1);
circularLinkedList.printList();

console.log(circularLinkedList);