연결리스트 - 구현

연결리스트를 구현하기에 앞서 알아야할 단어 추상 자료형 이다.

어떤 데이터와 그 데이터에 대한 연산을 표기하는 것.

🙋🏻‍♀️ 너무 어렵다 무슨 말이야??

세탁기로 예를 들면

세탁기로 빨래를 하기 위해서는 옷이 필요하다. 여기서 옷이 어떠한 데이터이다. 그리고 세탁기에는 이 옷(데이터)을 처리하는 여러 가지 기능(연산)이 있다.
빨래, 탈수, 남은 시간, 배수
세탁기의 여러가지 기능만 나열했을 뿐 구체적인 구현 방법은 없다.

이렇게 데이터와 그 데이터를 연산하는 기능을 표기하는 것을 추상 자료형이라고 부른다.

📌 연결리스트의 추상자료형

데이터는 정수라고 가정하고 추상 자료형을 자바스크립트로 표현하면 아래와 같다.

1) 모든 데이터 출력 printAll()

• 연결리스트의 모든 원소를 출력하는 기능
  

2) 모든 데이터 제거 clear()

• 연결리스트의 모든 원소를 제거하는 기능

3) 인덱스 삽입 insertAt(index, data)

• 원하는 인덱스에 데이터를 삽입하는 기능

4) 마지막 삽입 insertLast(data)

• 마지막 데이터 뒤에 데이터를 삽입하는 기능

• 인덱스 삽입으로도 마지막 원소뒤에 삽입이 가능하지만 마지막 위치를 따로 계산해야 하기 때문에 따로 만드는 것이 좋다고 판단했다.

5) 인덱스 삭제 deleteAt(index)

• 원하는 인덱스에 데이터를 삭제하는 기능

6) 마지막 삭제 deleteLast()

• 마지막 데이터를 제거하는 기능
  

7) 인덱스 읽기 getNodeAt(index)

• 원하는 인덱스에 있는 데이터를 읽는 기능

📌 추상자료형을 기반으로 구현을 해보자.

• 연결리스트는 데이터를 담은 노드를 서로 연결하는 구조다. 이를 위해 가장 먼저 노드를 만들어준다.

• Node 라는 이름의 class 선언해준다.

• 클래스틑 인스턴스화 했을 때 자동으로 호출되는 생성자를 만들어준다. 일반적으로 생성자에서 초기화를 해준다.

• 생성자의 매개변수로 data와 next를 만들어준다. next는 기본값으로 null로 설정해준다.

• 매개변수 data는 필수지만, next는 입력하지 않는다면 null이 할당된다.

• 자바스크립트 클래스 내에 변수를 프로퍼티라고 한다, 생성자 내에서 data와 next 프로퍼티를 만들어 매개변수 data와 next로 초기화해준다.

  

[text.mjs] 에서 node Class import 해준다. node Class를 이용해서 간단한 text 코드를 작성해보자.

• 정수 1이 저장된 'node1'을 만들어준다.

• 차례로 'node2', 'node3'도 만들어준다.

• node1의 next를 node2로 설정해 연결해준다. 그리고 node2의 next를 node3로 설정해 연결해준다.
  

연결이 잘 됐는지 출력해보자 > 굿 !

자, 이제 본격적으로 연결리스트를 만들어보자

• [LinkedList,mjs] 을 열어 LinkedList 클래스를 선언해준다.

• 바로 생성자를 만들어주는데 이번엔 매개변수가 필요없다.

• 연결리스트의 시작 노드를 가리키는 head와 총 저장된 노드의 수를 저장하는 count 프로퍼티를 만들어 초기화해준다.
  

✅ 이제 원하는 인덱스에 데이터를 삽입하는 insertAt() 함수를 만들어준다.

• 먼저 함수의 원형을 만들어준다.

• 삽입할 위치를 뜻하는 index와 삽입할 데이터를 뜻하는 data 매개변수를 만들어준다.

• 그리고 가장 먼저 예외 처리를 해준다.

• 연결리스트의 크기보다 큰 곳에 삽입하거나 음수 위치에 삽입하는 경우 에러를 발생시킨다.
  

• 삽입할 노드 생성하기 > 매개변수 data를 Node의 생성자로 넘겨줘서 Node의 data를 설정해준다.
  

이제 새로 생성된 노드를 연결하면 되는데 두 가지 상황을 고려해서 만들어보자.

• 1️⃣ 리스트의 가장 앞부분에 삽입하는 경우로 새로 삽입하는 노드가 head가 되는 경우

• 2️⃣ 가장 앞부분을 제외한 나머지 부분에 삽입하는 경우로 head 노드에서 next로 목표 인덱스까지 게속 참조해서 가는 경우

위 두 가지를 고려해서 코드를 짜보자.

• if 문에서 리스트의 가장 앞부분에 삽입하는 경우, 즉 인덱스가 0인 경우를 처리하고
  - 새로 생성한 노드의 next가 head를 가리키게 하고, 새로 생성한 노드를 head로 변경한다.

• else 문에서는 가장 앞부분 삽입을 제외한 경우를 처리한다.
  - 원하는 인덱스까지 노드를 타고 들어가서 새로 삽입하는 경우
  - 만약 인덱스 3에 삽입한다면 head 노드에서 세 번째 떨어진 노드에 삽입하는 경우이다.
  - currentNode로 세 번째 떨어진 노드 전까지 이동하고 newNode가 curretNode가 가리키던 노드, 즉 세 번째 노드(9)를 가리키게 한다. 그리고 currentNode(7)가 새로운 노드(data)를 가리키게 하면 끝난다.
  

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

class LinkedList {
  constructor() {
    this.head = null;
    this.count = 0;
  }
  insertAt(index, data) {
    // 예외처리
    if (index > this.count || index < 0) {
      throw new Error("범위를 넘어갔습니다.");
    }
    // 삽입할 노드 생성
    let newNode = new Node(data);
    // if 문에서 리스트의 가장 앞부분에 삽입하는 경우, 즉 인덱스가 0인 경우를 처리하고
    if (index == 0) {
      // 새로 생성한 노드의 next가 head를 가리키게 하고,
      newNode.next = this.head;
      // 새로 생성한 노드를 head로 변경한다.
      this.head = newNode;
      // else 문에서는 가장 앞부분 삽입을 제외한 경우를 처리한다.
      // 원하는 인덱스까지 노드를 타고 들어가서 새로 삽입하는 경우
      // 만약 인덱스 3에 삽입한다면 head 노드에서 세 번째 떨어진 노드에 삽입하는 경우이다.
      // currentNode로 세 번째 떨어진 노드 전까지 이동하고 newNode가 curretNode가 가리키던 노드,
      // 즉 세 번째 노드(9)를 가리키게 한다.
      // 그리고 currentNode(7)가 새로운 노드(data)를 가리키게 하면 끝난다.
    } else {
      // 먼저 삽입하려는 노드 바로 전까지 가기 위한 변수를 하나 만든다.
      // head에서 시작하기 때문에 head로 초기화해준다.
      let currentNode = this.head;
      // 목표 인덱스 바로 전까지 next를 이용해 currentNode를 이동시킨다.
      // 만약 목표 인덱스가 3이라고 하면 currentNode는 두 번째 떨어진 노드(7)까지 접근한다.
      for (let i = 0; i < index - 1; i++) {
        currentNode = currentNode.next;
      }
      // 목표 인덱스의 바로 전 노드까지 왔다면 이제 간단하다.
      // 새로운 노드가 currentNode의 next 노드를 가리키고
      newNode.next = currentNode.next;
      // currentNode(7)가 새로운 노드를 가리키면 된다.
      currentNode.next = newNode;
    }
    // 새로운 노드가 삽입되었으니 if 문과 else 문 밖에 count를 하나 올려준다.
    this.count++;
  }
}

export { Node, LinkedList };

[test.mjs] 파일을 열어서 LinkedList 파일 import 해주고 실행결과를 확인해보자.

이제 연결리스트의 insertAt() 함수를 테스트해보자.

• 먼저 연결리스트를 인스턴스화 해주고 , 가독성을 위해 insertAt()을 호출했다는 메세지를 출력해준다.

• 0 부터 4까지 다섯 개의 데이터를 삽입해준다.

import { Node, LinkedList } from "./LinkedList.mjs";

let node1 = new Node(1);
let node2 = new Node(2);
let node3 = new Node(3);

node1.next = node2;
node2.next = node3;

console.log(node1.data);
console.log(node1.next.data);
console.log(node1.next.next.data);

let list = new LinkedList();

console.log("=== insertAt() 다섯 번 호출 ===");
list.insertAt(0, 0);
list.insertAt(1, 1);
list.insertAt(2, 2);
list.insertAt(3, 3);
list.insertAt(4, 4);

✅ 연결리스트의 모든 원소를 출력하는 printAll()

• [LinkedList] 파일 안에 printAll() 함수를 만들어준다, printAll() 함수는 아주 단순 !

 printAll() {
    //먼저 currentNode 변수가 head를 가리키게한다.
    let currentNode = this.head;
    // 리스트의 끝까지 순회하는데 currentNode가 null이 될 때까지 계속 next 노드를 참조해주면 된다.
    while (currentNode != null) {
      // next 노드로 이동 전에 currentNode를 출력해주고
      console.log(currentNode.data);
      // currentNode를 currentNode의 next노드로 가리킨다.
      currentNode = currentNode.next;
    }
  }

• [test.mjs] 파일을 열어서 printAll() 함수를 호출해준다.

• 터미널에서 node로 파일을 실행한다.

• insertAt() 다섯번 호출 밑으로 모든 데이터가 출력된 것을 확인할 수 있다.

• [0,1,2,3,4]처럼 한 줄에 출력하기 위해 코드를 수정해보자.

  printAll() {
    //먼저 currentNode 변수가 head를 가리키게한다.
    let currentNode = this.head;
    // 1️⃣ text변수에 문자열로 대괄호를 넣어준다.
    let text = "[";
    // 리스트의 끝까지 순회하는데 currentNode가 null이 될 때까지 계속 next 노드를 참조해주면 된다.
    while (currentNode != null) {
      // 2️⃣text 변수에 currentNode의 데이터를 저장해준다.
      text += currentNode.data;
      // currentNode를 currentNode의 next노드로 가리킨다.
      currentNode = currentNode.next;

      // 3️⃣ currentNode가 마지막 데이터가 아니라면 콤마로 구분해준다
      if (currentNode != null) {
        // 모든 노드를 순회했다면 text에는 "[0,1,2"와 같이 저장되어있다.
        text += ", ";
      }
    }
    // 4️⃣ text 변수에 닫는 대괄호를 넣어서 모양을 완성시켜준다.
    text += "]";
    // text 변수 출력
    console.log(text);
  }

✅ clear()

• clear() 함수는 리스트의 모든 원소를 제거하는 기능이다.

[LinkedList.mjs]

  // 📌 clear
  // head가 null을 가리키게 해서 참조하는 것이 없게 만들어주고
  clear() {
    this.head = null;
    // count를 0으로 만들어주면 리스트는 비워진다.
    this.count = 0;
  }

• [test.mjs]에서 테스트해보기
  
• insertAt() 함수로 리스트에 [0,1,2,3,4]가 있었지만 clear() 함수 호출로 모두 비워진 것을 확인할 수 있다.

✅ insertLast()

• 마지막 데이터 뒤에 삽입하는 기능으로 insertAt() 함수를 이용하면 아주 쉽게 구현할 수 있다.

[LinkedList.mjs]

  //  1️⃣ 먼저 함수를 정의해준다.
  insertLast(data) {
    // 2️⃣ insertAt() 함수를 호출해서 indext에 리스트의 크기인 count를 넣어 가장 뒤에 데이터를 삽입한다.
    this.insertAt(this.count, data);
  }

• [test.mjs] 에서 insertLast() 함수를 호출하는 텍스트를 호출해주고,
• clear() 함수로 비워진 리스트에 insertLast() 함수로 0,1,2를 넣어준다.
• printAll() 함수를 호출해 리스트를 출력한다.
  

✅ insertAt() 함수의 반대기능을 하는 deleteAt() 함수

• deleteAt() 함수는 함수의 매개변수로 인덱스만 받으면 제거할 수 있으므로 data는 필요없다.

[LinkedList.mjs]

  deleteAt(index) {
    // 1️⃣ insertAt() 함수와 마찬가지로 에러처리를 해준다.
    // 리스트의 크기를 넘어서면 에러를 발생시킨다.
    if (index >= this.count || index < 0) {
      throw new Error("제거할 수 없습니다.");
    }

    // 2️⃣ 노드를 순회할 변수(currentNode)를 만들어준다.
    let currentNode = this.head;
    // insertAt() 함수와 마찬가지로 두 가지 상황을 고려한다. if문 사용
    // 1) head 노드, 즉 첫 번째 노드를 제거하는 상황
    if (index == 0) {
      // 삭제된 노드를 리턴하기 위해 삭제될 노드를 저장
      let deletedNode = this.head;
      // head를 head의 next 노드로 설정해준다.
      this.head = this.head.next;
      // 삭제됐으니 count도 하나 줄여준다.
      this.count--;
      // 삭제된 노드(deletedNode)는 리턴해준다.
      return deletedNode;
    } else {
      // 2) 첫 번째 노드를 제외한 나머지 노드를 제거하는 상황
      // for 문드로 제거할 노드 이전 노드까지 순회한다.
      for (let i = 0; i < index - 1; i++) {
        currentNode = currentNode.next;
        //for문을 마치면 currentNode는 제거할 노드(7)의 이전 노드를 가리킨다.
      }
      // 제거한 노드는 반환되어야 하므로 변수에 저장해준다.
      let deletedNode = currentNode.next;
      // 이제 제거할 노드의 이전 노드(currentNode)가 제거할 노드의 next노드(9)를 가리키게 해주겠다.
      currentNode.next = currentNode.next.next;
      // 삭제를 했으니 count를 하나 줄여주고 삭제되 노드를 리턴해준다.
      this.count--;
      return deletedNode;
    }
  }

• [test.mjs] 에서 deleteAt() 함수를 호출하는 텍스트를 호출한다.
  

✅ deleteLast()

• deleteAt() 함수를 이용하면 간단하게 구현할 수 있다.

[LinkedList.mjs]

  deleteLast() {
    //1️⃣ deleteAt 함수 호출하는데 index는 리스트의 카운터보다 1 작은 값을 넘겨준다.
    // 만약 데이터가 세 개라면 2번 인덱스가 마지막 데이터이기 때문이다.
    return this.deleteAt(this.count - 1);
  }

• [test.mjs] 에서 deleteLast() 함수를 호출하는 텍스트를 호출한다.

• 에러 발생

• 이 에러는 리스트에 데이터가 존재하지 않는데 deleteLast()함수를 호출해서 발생한 에러이다.

• 데이터가 두 개인데 deleteLast() 함수를 세 번 호출했기 때문이다.

• deleteLast 함수를 한 개 지워주면 에러는 사라진다.

✅ 추상자료형의 마지막인 getNodeAt()

• getNodeAt() 함수는 해당 인덱스의 노드를 읽는 기능이다.

[LinkedList.mjs]

// 매개변수는 읽으려는 Index를 넣어준다.
  getNodeAt(index) {
    // 읽고자 하는 인덱스가 리스트 범위를 넘어갈 때 에러를 발생시켜주겠다.
    if (index >= this.count || index < 0) {
      throw new Error("범위를 넘어갔습니다.");
    }
    // 리스트를 순회할 변수를 만들고 head와 같은 노드를 가리킨다.
    let currentNode = this.head;
    // 이제 currentNode가 해당 인덱스까지 순회한다.
    for (let i = 0; i < index; i++) {
      currentNode = currentNode.next;
    }
    // currentNode를 리턴해주면 끝이다.
    return currentNode;
  }

• [test.mjs] 에서 getNodeAt() 함수로 두 번째 index의 노드를 가져온다.
  
• 두 번째 index의 노드, 즉 세 번째 데이터가 잘 출력된 것을 확인할 수 있다.

지금까지 연결 리스트의 추상 자료형을 정의하고, 이걸 바탕으로 구현까지 해봤다. 연결 리스트를 만들어보면서 노드를 이해했는데, 이렇게 만들어본 경험으로 연결 리스트의 장단점이 기억나지 않더라도 머리로 그려보면 특성을 알 수 있기 때문에 굳이 외우지 않아도 된다.

연결 리스트는 이후에 배울 스택과 큐를 구현하는데 쓰이기 때문에 확실하게 이해해야 한다...!!!

with 그림으로 쉽게 배우는 자료구조와 알고리즘