[JavaScript] 자료구조 - 연결 리스트

Flex·2022년 3월 18일

algorithm

알고리즘 모음

목록 보기

2/3

🌿 프로토타입 (Prototype)

어떠한 객체가 만들어지기 위해 객체의 모태가 되는 원형입니다.

JavaScript는 일반적인 객체지향 언어와는 다르게,
프로토타입을 이용한 복사(Cloning)를 통해 새로운 객체를 생성합니다.

일반적인 객체 생성 방식

속성은 생성자에서 정의
메서드는 프로토타입에서 정의

🌿 연결 리스트 (Linked List)

각 노드가 데이터와 포인터를 가지며, 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조입니다.

1. 일반적인 특성

각각의 노드(Node)들로 구성되어 있습니다.
head 는 처음 노드를 가리킵니다.
하나의 노드는 해당 노드의 데이터값인 data 와 다음 노드를 가리키는 포인터인 next 를 가집니다.
다음 노드가 존재하지 않을 경우 next=null 이 됩니다.

2. 노드의 코드

// Node(): data와 point를 가지고 있는 객체
function Node(data) {
  this.data = data;
  this.next = null;
}

연결 리스트에서 노드는 데이터값과 다음 노드를 가리키는 포인터를 가집니다.
노드만 딸랑 하나 만들면 값만 들어가고, 다음 노드로 연결되어있지는 않은 상태이죠.

3. 연결 리스트의 코드

// LinkedList(): head와 length를 가지고 있는 객체
function LinkedList() {
  this.head = null;
  this.length = 0;
}

그래서 우리는 가장 첫번째 노드를 가리키는 head 와 length 길이를 가지는 연결 리스트를 구현하여 노드들을 연결시킵니다.

연결 리스트와 관련된 다양한 메서드를 직접 만들어 구현할 수 있는데, 대표적인 삽입과 삭제는 꼭! 익히고 넘어갑시다.
이는 응용하여 뒤의 이중 연결 리스트와 원형 연결 리스트에서도 비슷한 구조로 사용할 수 있습니다.

4. 연결 리스트 끝에 노드 추가하기

// append(): 연결 리스트의 가장 끝에 노드 추가
LinkedList.prototype.append = function (value) {
  let node = new Node(value);
  let current = this.head;

  if (this.head === null) {
    this.head = node;
  } else {
    while (current.next != null) {
      current = current.next;
    }
    current.next = node;
  }

  this.length++;
};

value 값을 가지는 새로운 노드를 생성합니다.
head 를 가리키는 변수를 설정해줍니다.
연결 리스트의 마지막까지 탐색하면서 가장 끝자리에 해당 노드를 넣어줍니다.
3-1. 연결 리스트가 비어있으면? (this.head === null) --> head 에 바로 넣어주면 되겠죠!
3-2. 다음 노드가 없으면? --> 바로 우리가 찾던 자리입니다! next 자리에 노드를 연결해줍시다.
마지막으로 연결리스트의 길이를 증가시킵니다.

5. 지정 위치에 노드 추가하기

// insert(): position 위치에 노드 추가
LinkedList.prototype.insert = function (value, position = 0) {
  if (position < 0 || position > this.length) return false;

  let node = new Node(value),
    current = this.head,
    index = 0,
    prev;

  if (position === 0) {
    node.next = current;
    this.head = node;
  } else {
    while (index++ < position) {
      prev = current;
      current = current.next;
    }

    node.next = current;
    prev.next = node;
  }

  this.length++;

  return true;
};

연결 리스트의 지정 위치에 노드를 삽입하는 건 신경쓸게 한가지 늘어납니다.

중간 지점의 연결을 무턱대고 끊은 후 연결하려고 하면 이전에 연결했던 지점이 어딘지도 모르고, 연결이 당연히 안되겠죠?
해당 메서드를 구현하려면 prev 등의 이름으로 이전 노드를 기억하며 삽입할 위치를 찾아나가야 합니다.
위 코드를 천천히 살펴보면 append 메서드와 형식은 동일하다는걸 알 수 있을거에요!

6. 특정 값을 가지는 노드 삭제하기

// remove(): value 데이터를 찾아 노드 삭제
LinkedList.prototype.remove = function (value) {
  let current = this.head;
  prev = current;

  while (current.data != value && current.next != null) {
    prev = current;
    current = current.next;
  }

  if (current.data != value) return null;

  if (current === this.head) {
    this.head = current.next;
  } else {
    prev.next = current.next;
  }

  this.length--;

  return current.data;
};

우리가 구현한 연결 리스트에서는 단일 방향으로만 탐색 가능합니다.

따라서 insert 메서드와 비슷하게 삭제 메서드도 구현이 가능해요.
목표 노드를 삭제 후 이전 노드와 다음 노드를 연결해야 하기 때문에 이전 노드를 기억하는 변수가 필요합니다!