[자료구조 | JS ] 단일 연결 리스트(single linked list)와 배열(Array)

단일 연결 리스트와 JS의 배열의 가장 큰 차이는 index유무이다. 연결 리스트는 단순히 포인터로 연결된 노드의 집합이며 index를 가지고 있지 않아 특정 값에 접근하는데 적합하지 않다. 배열의 경우 index를 가지고 있어 특정 값을 읽어오는 것에 능하다. 메모리 상에 연속적으로 저장되어있는 특정을 갖기 때문이다. 

 

데이터 탐색에는 배열이 용이하고 추가와 삭제의 경우는 연결리스트가 용이하다.

 

배열(Array)

• 입력된 데이터들이 메모리 공간에서 연속적으로 저장되어있는 자료구조 
• 메모리 상에 연속적으로 저장되어있는 특징 index를 통한 접근 용이(임의 접근 가능)
• 배열의 크기는 처음 생성할 때 정하며 이후에는 변경 불가-> 배열은 정적(static)인 자료구조

연결 리스트(linked list)

• 동적인 자료구조 -> 크기를 미리 정할 필요 x 
• 배열처럼 연속된 메모리 주소를 할당받지 않음 
• 노드로 이루어져 있으며, 해당 노드는 저장된 데이터 값과 다음 데이터가 있는 메모리 주소(단일 연결 리스트의 경우)를 가지고 있다. 말하자면 다음 노드의 포인터를 가지고 있다?
• 장점으로는 배열의 크기에 제한이 없다. 데이터 추가 삭제가 굉장히 자유롭다. 
• 임의 접근 불가(특정 데이터에 접근) -> 때문에 데이터 탐색 방식이 순차접근이다.

JS class로 단일 연결 리스트와 관련 메서드 구현하기 

• (방향: 맨 뒤)push, pop, (방향: 맨 앞)shift, unshift

// TODO: Node와 push() 구현하기
class Node {
  constructor(val) {
    //처음에는 next가 없기 때문에 null로 초기화
    this.val = val;
    this.next = null;
  }
}

{
  let first = new Node('hi');
  first.next = new Node('there');
  first.next.next = new Node('bye');
  // ! 위의 방법은 연결 리스트를 표현하는 아주 좋지 않은 방법
}

class SinglyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }
  push(val) {
    //만일 리스트가 비어있지 않다면, 마지막 노드의 "next"를 새롭게 생성된 노드를 가리키도록 하고
    // tail이 새롭게 생성된 노드를 가리키도록 설정, 그리고 길이를 하나 늘려주면된다.

    let newNode = new Node(val);
    if (!this.head) {
      //주어진 값을 받아들인 후 그것을 이용해 새로운 노드를 생성하는 것이 전부
      // *head가 리스트에 없다면 head 와 tail 을 주어진 값으로 세팅(완전 처음)
      this.head = newNode;
      this.tail = this.head;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }
    this.length++;
    //전체 리스트 반환(this)
    return this;
    //단지 tail을 이용해 리스트의 마지막에 새로운 노드를 추가하고 테일을 맨 끝을 
    //가리키도록 한 자리 움직여주면 된다.
  }

  // traverse() {
  //   let current = this.head;
  //   // current의 값이 next로 향하게 포인터를 수정해주고 값이 있다면 다시 console.log
  //   while (current) {
  //     console.log('current.val', current.val);
  //     current = current.next;
  //   }
  // }
  pop() {
    //인자를 하나도 받지 않으며 맨 뒤에있는 요소를 뽑아내는 메서드
    if (!this.head) return undefined;
    let current = this.head;
    let newTail = current;

    // * while루프는 current가 더 이상 앞으로 나아갈 수 없을 때까지 반복
    while (current.next) {
      //newTail은 항상 current가 이전에 가리키던 것으로 설정
      newTail = current;
      current = current.next;
    }
    this.tail = newTail;
    this.tail.next = null;
    this.length--;
    console.log('current', current);
    if (this.length === 0) {
      //이제 리스트에 값이 없다는 뜻 pop된 요소가 마지막요소라서
      this.head = null;
      this.tail = null;
    }
    return current; //제거되는 마지막 node
  }

  shift() {
    if (!this.head) return undefined;
    let currentHead = this.head;
    //this.head는 newHead가 된 것
    this.head = currentHead.next;
    this.length--;
    if (this.length === 0) {
      this.tail = null;
    }
    console.log('currentHead', currentHead);
    return currentHead;
  }

  unshift(val) {
    // 1. val을 담은 새로운 노드를 만들어준다.
    let newNode = new Node(val);
    // 2. head가 없다면(노드 자체가 없음)
    if (!this.head) {
      this.head = newNode;
      this.tail = this.head;
    } else {
      newNode.next = this.head;
      this.head = newNode;
    }

    this.length++;
    return this;
  }
}

let list = new SinglyLinkedList();

list.unshift('FIRST');

console.log('list', list);

// TODO: Popping 구현하기
// push() 보다 까다로운 점은 마지막 노드를 제거해야 한다는 것이다.
// 또한, 테일이 새로운 마지막 노드를 가리키도록 해야 하는데 역방향 포인터를 가지고 있지 않기 
// 때문이다. -> tail로는 그 전의 노드를 그냥 알 수 없다.(역방향 포인터x)

// * 마지막에 두 번째 노드를 추적해야하기 때문에 두 개의 변수를 유지해야 한다.

// TODO: Shifting 구현하기
// shift() 메소드는 연결 리스트 앞에서 노드를 제거한다. pop은 맨 뒤에서 꺼내기,shift는 맨 앞에서 꺼내기
// * 현재 헤드가 가리키고 있는 노드를 제거한 후, 헤드를 헤드가 가리키고 있던 리스트의 두번째 노드를 가리키도록 한다.
// if empty, do nothing
// temp = head
// head = head.next
// delete temp

// TODO: Unshifting 구현하기
// * 새로운 노드를 리스트에 추가하는 한 방법, push와 달리 맨 앞에 노드를  추가하는 방법(shifting과 반대)

🔺Circular reference Error in JS

unshift()를 구현하면서 else 블록으로 묶어놓은 부분을 블록 밖에서 실행시켰을 때, 아래와 같은 에러메세지가 떴다. 

if절에서는 !this.head (리스트에 노드가 없으면)이라는 조건에서 세팅을 해주고 있는데 아래 2줄의 코드를 else 블록에 묶지 않으면 무조건 실행되는 코드가 된다. 노드가 여러개 존재한다면 문제가 되지 않지만 노드가 비었을 경우에는 같은 노드를 계속해서 순환하면서 포인팅하는 오류가 생긴다. 

ref * 1이라는 레퍼런스를 순환해서 계속 참조한다는 표시

Ciruclar reference 관련 에러 정리 포스팅 사이트