자료구조 - 배열과 연결 리스트/ js 연결리스트 구현

배열 : 일정한 메모리 공간을 차지하는 여러 요소들이 순차적으로 나열된 자료구조

- 각 요소에는 0부터 시작하는 고유한 순서 번호인 index 가 매겨진다
- index로 요소 식별

*배열과 유사한 컴퓨터 부품 : RAM
- 어떤 주소에 접근하든 접근 시간이 일정하다. -O(1)


배열의 확장
- 2차원 배열 : 배열 속에 배열이 포함된 경우.
행, 열 식별할 2개의 index 필요

js에서는 let arr = [][]; 와 같은 2차원 배열 선언이 불가
하지만, 약간의 트릭을 통해 2차원 배열과 비슷한 배열을 만들 수 있다

ex)
1. 초기값 할당

// arr[5][2]
var arr = [['a','b'], ['c', 'd'], ['e', 'f'], ['g', 'h'], ['i', 'j']];

2. for문 사용

// arr[5][2]
var arr = new Array(5);

for (var i = 0; i < arr.length; i++) {
    arr[i] = new Array(2);
}

3. ES6 이상 지원시 가능한 방법

// arr[5][2] (빈 배열 생성)
const arr1 = Array.from(Array(5), () => new Array(2)

// arr[5][2] (null로 초기화하여 생성)
const arr2 = Array.from(Array(5), () => Array(2).fill(null))

- 3차원 배열 : 배열 속의 배열 속의 배열이 포함된 경우
행, 열, 깊이 3개의 index 필요

---

연결 리스트 : 노드의 연결로 구성된 자료구조

노드
- 저장하고자하는 데이터
- 다음 노드의 위치(메모리상 주소) 정보

연결리스트의 첫번째 노드는 헤드 head, 마지막 노드는 꼬리 tail 이라고 부른다

모든 노드는 메모리 내에 순차적으로 저장되어있을 필요가 없다.
- 연속적으로 구성된 데이터를 불연속저긍로 저장할 때 유용하게 사용할 수 있음
*노드가 더 이상 없다 - 는 null로 표기

추가와 삭제 연산에서 강점을 갖는다.
- 배열과 달리, 재정렬이 불필요하다. (연결 관계, 다음 노드의 위치만 변경하면 됨)


[js 연결 리스트 구현]

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

싱글 연결 리스트
한쪽 방향으로만 탐색
(단방향 탐색. 다음 노드의 위치만 알 수 있고 이전 노드 위치는 알기 어려움)

//singly linked list, 싱글 연결 리스트
class SinglyLinkedList {
  constructor() {
    this.head = null;
  }

  append(value) {
    const newNode = new Node(value);
    if (!this.head) {
      this.head = newNode;
      return;
    }

    let current = this.head;
    while (current.next) current = current.next;
    current.next = newNode;
  }

  print() {
    let current = this.head;
    const values = [];
    while (current) {
      values.push(current.value);
      current = current.next;
    }
    console.log(values.join(" -> "));
  }
}

const singlyLinkedList = new SinglyLinkedList();
singlyLinkedList.append(1);
singlyLinkedList.append(2);
singlyLinkedList.append(3);
singlyLinkedList.print(); // 1 -> 2 -> 3

이중 연결 리스트
이전 위치 정보도 포함(양방향 탐색 가능)
저장 공간 필요 - 한 노드에 2개의 위치 정보 포함

// doubly linked list, 이중 연결 리스트
class DoublyLinkedListNode {
  constructor() {
    this.head = null;
  }

  append(value) {
    const newNode = new Node(value);

    if (!this.head) return (this.head = newNode);

    let current = this.head;
    while (current.next) current = current.next;
    current.next = newNode;
    newNode.prev = current;
  }

  printForward() {
    let current = this.head;
    const values = [];
    while (current) {
      values.push(current.value);
      current = current.next;
    }
    console.log(values.join(" <-> "));
  }

  printBackward() {
    let current = this.head;
    while (current.next) current = current.next;

    const values = [];
    while (current) {
      values.push(current.value);
      current = current.prev;
    }
    console.log(values.join(" <-> "));
  }
}

const doublyLinkedList = new DoublyLinkedListNode();
doublyLinkedList.append(1);
doublyLinkedList.append(2);
doublyLinkedList.append(3);
doublyLinkedList.printForward(); // 1 <-> 2 <-> 3
doublyLinkedList.printBackward(); // 3 <-> 2 <-> 1

환형 연결 리스트, circular linked list (원형 연결 리스트)
tail 노드가 head 노드를 가리켜 노드들이 원형으로 구성된 연결 리스트

// circular linked list, 환형 연결 리스트
// 환형 연결 리스트는 마지막 노드가 첫 번째 노드를 가리킴
class CircularSinglyLinkedList {
  constructor() {
    this.head = null;
  }

  append(value) {
    const newNode = new Node(value);
    if (!this.head) {
      this.head = newNode;
      newNode.next = this.head;
      return;
    }

    let current = this.head;
    while (current.next !== this.head) current = current.next;
    current.next = newNode;
    newNode.next = this.head;
  }

  print(limit = 10) {
    const values = [];
    let current = this.head;
    let count = 0;

    while (current && count < limit) {
      values.push(current.value);
      current = current.next;
      count++;
    }

    console.log(values.join(" -> ") + " -> ... ");
  }
}

const circularSinglyLinkedList = new CircularSinglyLinkedList();
circularSinglyLinkedList.append(1);
circularSinglyLinkedList.append(2);
circularSinglyLinkedList.append(3);
circularSinglyLinkedList.print(); // 1 -> 2 -> 3 -> 1 -> 2 -> 3 -> 1 -> 2 -> 3 -> 1 -> ...

이중 연결 리스트로 구현된 환형 연결 리스트

// circular doubly linked list, 환형 이중 연결 리스트
// 환형 이중 연결 리스트는 각 노드가 이전 노드와 다음 노드를 가리키고, 마지막 노드가 첫 번째 노드를 가리킴
class CircularDoublyLinkedList {
  constructor() {
    this.head = null;
  }

  append(value) {
    const newNode = new Node(value);

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

    const tail = this.head.prev;

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

  printForward(limit = 10) {
    const values = [];
    let current = this.head;
    let count = 0;
    while (current && count < limit) {
      values.push(current.value);
      current = current.next;
      count++;
    }
    console.log(values.join(" <-> ") + " <-> ...");
  }

  printBackward(limit = 10) {
    const values = [];
    let current = this.head?.prev;
    let count = 0;
    while (current && count < limit) {
      values.push(current.value);
      current = current.prev;
      count++;
    }
    console.log(values.join(" <-> ") + " <-> ...");
  }
}

const circularDoublyLinkedList = new CircularDoublyLinkedList();
circularDoublyLinkedList.append(10);
circularDoublyLinkedList.append(20);
circularDoublyLinkedList.append(30);
circularDoublyLinkedList.printForward(); // 10 <-> 20 <-> 30 <-> 10 <-> 20 <-> 30 <-> 10 <-> 20 <-> 30 <-> 10 <-> ...
circularDoublyLinkedList.printBackward(); // 30 <-> 20 <-> 10 <-> 30 <-> 20 <-> 10 <-> 30 <-> 20 <-> 10 <-> 30 <-> ...
circularDoublyLinkedList.printForward(5); // 10 <-> 20 <-> 30 <-> 10 <-> 20 <-> ...
circularDoublyLinkedList.printBackward(5); // 30 <-> 20 <-> 10 <-> 30 <-> 20 <-> ...