🌿 프로토타입 (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++;
};

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

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 메서드와 비슷하게 삭제 메서드도 구현이 가능해요.
목표 노드를 삭제 후 이전 노드와 다음 노드를 연결해야 하기 때문에 이전 노드를 기억하는 변수가 필요합니다!

1. 노드의 값이 일치하지 않고 다음 노드가 존재하면 다음 노드로 넘어갑니다.
2. 마지막까지 갔는데 일치하는 값이 없어요! --> null
3. head 가 삭제할 값이랑 동일해요! --> head 가 next 를 가리키도록 합니다.
4. 삭제할 노드에 위치해있어요! --> prev (이전 노드) 의 다음을 현재 노드의 다음과 연결합니다.
5. 마지막으로 연결 리스트의 길이를 감소시킵니다.

🌿 이중 연결 리스트 (Double Linked List)

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

특징

• 단일 연결 리스트의 노드와 다르게 양방향으로 포인터를 가집니다.
• 뒤에서부터 시작할 수 있는 tail 이 존재합니다.
• 이전 노드에 접근할 수 있는 prev 가 존재합니다.
• 관리해야 할 포인터가 두가지 --> 사용 시 주의가 필요합니다.

본문 내용이 과도하게 길어지는걸 방지하기 위해
아래 구현 예제 코드의 링크를 첨부합니다.

구조는 단일 연결 리스트와 비슷합니다.
prev 를 설정하는 단계가 추가되었음을 명심하세요!

💡 이중 연결 리스트 구현 코드 보러 가기 - Github

🌿 원형 연결 리스트 (Circular Linked List)

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

특징

• 순환식 구조로 데이터를 가지며 연결되어 있습니다.
• 단일 연결 리스트와 다른 점은 단 하나,
  마지막 노드가 null 이 아닌 head 를 가리킵니다.
• 단일 연결 리스트처럼 data 와 next 만 가집니다.
• 삽입과 삭제 시 첫 노드와 마지막 노드가 이어지도록 구현이 필요합니다.

💡 원형 연결 리스트 구현 코드 보러 가기 - Github