단일 연결 리스트(Singly Linked List)

0. 요약

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

class SinglyLinkedList {
  constructor() {
    this.head = null;
    this.rear = null;
    this.size = 0;
  }

  // 단일 연결 리스트 맨 앞에 원소 추가하기
  unshift(data) {
    const node = new Node(data);
    if (!this.head) this.rear = node;

    node.next = this.head;
    this.head = node;
    this.size += 1;

    return this;
  }

  // 단일 연결 리스트 맨 뒤에 원소 추가하기
  push(data) {
    const node = new Node(data);
    if (this.size === 0) this.head = node;
    else this.rear.next = node;

    this.rear = node;
    this.size++;

    return this;
  }

  // 단일 연결 리스트 중간에 원소 추가하기
  insert(index, data) {
    if (index < 0 || index > this.size) return false;

    if (index === 0) return !!this.unshift(data);

    if (index === this.size) return !!this.push(data);

    const node = new Node(data);

    let prev = this.get(index - 1);
    node.next = prev.next;
    prev.next = node;

    this.size += 1;

    return true;
  }

  // 단일 연결 리스트의 원소 가져오기
  get(index) {
    if (index < 0 || index >= this.size) return null;

    if (index === this.size - 1) return this.rear;

    let cur = this.head;
    let count = 0;
    while (count < index) {
      cur = cur.next;
      count += 1;
    }
    return cur;
  }

  // 단일 연결 리스트의 첫번째 원소 삭제하기
  shift() {
    if (!this.head) return undefined;

    const currentHead = this.head;
    this.head = currentHead.next;
    this.size -= 1;

    if (this.size === 0) this.rear = null;

    return currentHead;
  }

  // 단일 연결 리스트의 마지막 원소 삭제하기
  pop() {
    if (!this.head) return undefined;

    let current = this.head;
    let newRear = current;

    while (current.next) {
      newRear = current;
      current = current.next;
    }

    newRear.next = null;
    this.rear = newRear;
    this.size -= 1;

    if (this.size === 0) {
      this.head = null;
      this.rear = null;
    }

    return current;
  }

  // 단일 연결 리스트의 중간 원소 삭제하기
  insert(index, data) {
    if (index < 0 || index > this.size) return false;

    if (index === 0) return !!this.unshift(data);

    if (index === this.size) return !!this.push(data);

    const node = new Node(data);

    let prev = this.get(index - 1);
    node.next = prev.next;
    prev.next = node;

    this.size += 1;

    return true;
  }

  // 단일 연결 리스트 초기화하기
  clearList() {
    this.head = null;
    this.rear = null;
    this.size = 0;
  }

  // 단일 연결 리스트의 모든 원소 출력하기
  printListData() {
    let cur = this.head;

    while (cur) {
      console.log(cur);
      cur = cur.next;
    }
  }

  // 단일 연결 리스트 역순으로 바꾸기
  reverse() {
    let head = this.head;
    let rear = this.rear;

    this.head = rear;
    this.rear = head;

    let prev = this.rear;
    let cur = this.rear.next;
    let count = 0;

    while (count < this.size - 1) {
      const temp = cur.next;
      cur.next = prev;
      cur = temp;
      prev = cur;

      count += 1;
    }

    this.rear.next = null;

    return this;
  }
}

---

1. 개요

배열과 함께 다른 자료 구조들을 구현하는 데 자주 사용되는 연결 리스트에 대해 살펴본다.

---

2. 연결 리스트란?

각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조이다. 연결 리스트는 자료의 추가와 삭제가 O(1)의 시간을 가능하다는 장점을 갖지만 특정 위치의 데이터를 검색해 내는데에는 O(n)의 시간이 걸리는 단점을 갖고 있다.

연결 리스트의 종류는 아래와 같다.

1. 단일(단방향) 연결 리스트

   • 각 노드에 자료 공간과 한 개의 포인터 공간이 있다.

   • 각 노드의 포인터는 다음 노드를 가리킨다.

2. 이중(양방향) 연결 리스트

   • 포인터 공간이 두 개가 있고 각각의 포인터는 앞의 노드와 뒤의 노드를 가리킨다.

3. 원형 연결 리스트

   • 일반적인 연결 리스트에 마지막 노드와 처음 노드를 연결시켜 원형으로 만든 구조이다.

현재 챕터에서는 단일 연결 리스트에 다루고 다음 챕터에서 이중 연결 리스트에 대해 다룬다.

---

3. 자바스크립트로 단일 연결 리스트 구현하기

단일 연결 리스트를 자바스크립트를 사용하여 구현해본다.

3-1. 노드와 연결 리스트의 기본 구조

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

노드의 기본구조는 자신이 가지는 값인 data와 자신으 뒤 노드의 값을 가리키는 next로 이루어진다. 만약 이중 연결 리스트라면 자신의 앞 노드를 가리키는 this.prev가 추가된다.

class SinglyLinkedList {
  constructor() {
    this.head = null;
    this.rear = null;
    this.size = 0;
  }
}

연결 리스트의 기본 구조로 맨 앞 노드인 head, 맨 뒤 노드인 rear 그리고 연결 리스트의 원소의 개수인 size로 구성된다.

3-2. 연결 리스트에 원소 추가하기

1. 연결 리스트 맨 앞에 원소를 추가하는 함수

   class SinglyLinkedList {
     // ...
     unshift(data) {
       const node = new Node(data);
       if (!this.head) this.rear = node;
   
       node.next = this.head;
       this.head = node;
       this.size += 1;
   
       return this;
     }
   }

   • 새로운 Node를 생성한다.

   • 만약 연결 리스트의 size가 0이라면 맨 뒤 노드인 rear 값을 새롭게 생성한 Node로 지정한다.

   • 생성한 Node의 뒤 노드 값을 현재 연결 리스트의 head로 지정한다.

   • 연결 리스트의 head에 새로운 Node가 들어간다.

   • 연결 리스트의 size를 하나 증가시킨다.

2. 연결 리스트 맨 뒤에 원소를 추가하는 함수

   class SinglyLinkedList {
     // ...
     push(data) {
       const node = new Node(data);
       if (this.size === 0) this.head = node;
       else this.rear.next = node;
   
       this.rear = node;
       this.size++;
   
       return this;
     }
   }

   • 새로운 Node를 생성한다.

   • 연결 리스트의 size가 0이라면 head의 값을 생성한 Node로 지정한다.

   • 연결 리스트의 size가 0이 아니라면 현재 연결 리스트의 rear의 뒤 노드의 값을 새롭게 생성한 Node로 지정한다.

   • 연결 리스트의 rear에 새로운 Node가 들어간다.

   • 연결 리스트의 size를 하나 증가시킨다.

   • 연결 리스트를 반환한다.

3. 연결 리스트 중간에 원소를 추가하는 함수

   class SinglyLinkedList {
     // ...
     insert(index, data) {
       if (index < 0 || index > this.size) return false;
   
       if (index === 0) return !!this.unshift(data);
   
       if (index === this.size) return !!this.push(data);
   
       const node = new Node(data);
   
       let prev = this.get(index - 1);
       node.next = prev.next;
       prev.next = node;
   
       this.size += 1;
   
       return true;
     }
   }

   • index가 0보다 작거나 연결 리스트의 크기보다 크다면 아무것도 리턴하지 않는다.

   • index가 0일 경우 연결 리스트 맨 앞에 원소를 추가하는 경우이다.

   • index가 size와 같을 경우 연결 리스트 맨 뒤에 원소를 추가하는 경우이다.

   • cur를 연결 리스트의 맨 앞에 위치한 원소로 지정한다.

   • next를 cur 앞이 원소로 지정한다.

   • count가 index보다 커질 때 까지 반복문을 돌린다.

   • 반복문 안에서 cur은 next가 되고 next는 next의 앞 원소가 된다.

   • 새롭게 생성한 노드가 cur과 next 사이에 들어간다.

3-3. 연결 리스트의 원소 가져오기

class SinglyLinkedList {
  // ...
  get(index) {
    if (index < 0 || index >= this.size) return null;

    if (index === this.size - 1) return this.rear;

    let cur = this.head;
    let count = 0;
    while (count < index) {
      cur = cur.next;
      count += 1;
    }
    return cur;
  }
}

• index가 0보다 작거나 연결 리스트의 크기보다 크다면 아무것도 리턴하지 않는다.

• index가 연결 리스트의 마지막(size-1) 번호라면 연결 리스트의 rear를 리턴한다.

• cur를 연결 리스트의 맨 앞에 위치한 원소로 지정한다.

• count가 index보다 작다면 while문을 실행한다.

• while문에서는 cur를 앞 원소로 바꾸고 count를 1증가시킨다.

• cur를 반환한다.

3-4. 연결 리스트의 원소 업데이트하기

class SinglyLinkedList {
  // ...
  set(index, data) {
    if (!this.get(index)) return false;

    let foundNode = this.get(index);
    foundNode.data = data;

    return true;
  }
}

3-5. 연결 리스트의 원소 삭제하기

1. 연결 리스트의 마지막 원소 삭제하기

   class SinglyLinkedList {
     // ...
     pop() {
       if (!this.head) return undefined;
   
       let current = this.head;
       let newRear = current;
   
       while (current.next) {
         newRear = current;
         current = current.next;
       }
   
       newRear.next = null;
       this.rear = newRear;
       this.size -= 1;
   
       if (this.size === 0) {
         this.head = null;
         this.rear = null;
       }
   
       return current;
     }
   }

   • head가 없다면 undefined를 반환한다.

   • 현재 바라보고 있는 노드를 current 변수에 할당한다.

   • 다음 rear될 노드를 newRear 변수에 할당한다.

   • current 노드의 다음 노드가 있을 때 반복문을 실행한다.

     • 반복문 내에서 newRear은 current가 된다.

     • 반복문 내에서 current는 다른 노드가 된다.

   • 반복문에서 나오게 될 때, current는 마지막 노드를 바라보게 된다.

   • 반복문에서 나오게 될 때, newRear는 마지막 노드의 이전 노드를 바라보게 된다.

   • newRear의 다음 노드를 null로 할당한 뒤 this.resr가 되도록 한다.

   • size를 1줄인다.

   • 만약 size가 0이 되었다면 this.head, this.rear은 모두 null이다.

   • 연결 리스트에서 끊어진 current 노드를 반환한다.

2. 연결 리스트의 첫번째 원소 삭제하기

   class SinglyLinkedList {
     // ...
     shift() {
       if (!this.head) return undefined;
   
       const currentHead = this.head;
       this.head = currentHead.next;
       this.size -= 1;
   
       if (this.size === 0) this.rear = null;
   
       return currentHead;
     }
   }

   • head가 없으면 undefined를 반환한다.

   • head를 변수(currentHead)에 저장을 한다.

   • head를 변수(currentHead)의 다음 노드로 바꾼다.

   • size를 1줄인다.

   • 만약 size가 0이 되었다면 더 이상 연결리스트에는 노드가 없는 것이기 때문에 rear을 null로 바꾼다.

   • 제거하려 했던 첫 번째 노드, 즉 currentHead 를 반환한다.

3. 연결 리스트의 특정 위치의 원소 삭제하기

   class SinglyLinkedList {
     // ...
     remove(index) {
       if (index < 0 || index >= this.size) return undefined;
   
       if (index === 0) return this.shift();
       if (index === this.size - 1) return this.pop();
   
       let prev = this.get(index - 1);
       let removed = prev.next;
       prev.next = prev.next.next;
   
       this.size -= 1;
   
       return removed;
     }
   }

   • index가 0보다 작거나 연결 리스트의 크기보다 크다면 아무것도 리턴하지 않는다.

   • cur를 연결 리스트의 맨 앞에 위치한 원소로 지정한다.

   • prev를 선언한다.

   • count의 기본값을 1로 한다.

   • index가 0인 경우 연결 리스트의 head를 cur의 앞에 위치한 원소로 지정한다.

   • 그 외의 경우 count가 index보다 작다면 반복문을 실행한다.

   • 반복문에서는 count값을 1증가시키고 prev를 cur로, cur를 cur의 앞에 위차한 원소를 지정한다.

   • 반복문이 종료되는 시점에는 cur값이 삭제되는 원소이다.

   • 그러므로 prev의 next를 cur의 앞에 위차한 원소로 바꾼다.

   • 연결 리스트의 size를 1감소시키고 삭제된 원소를 리턴한다.

3-6. 연결 리스트 초기화하기

class SinglyLinkedList {
  // ...
  clearList() {
    this.head = null;
    this.rear = null;
    this.size = 0;
  }
}

• head와 rear를 null로 바꾸고 size를 0으로 바꾼다.

• 메모리자체에는 Node가 남아있다.

3-7. 연결 리스트의 모든 원소 출력하기

class SinglyLinkedList {
  // ...
  printListData() {
    let cur = this.head;

    while (cur) {
      console.log(cur);
      cur = cur.next;
    }
  }
}

• cur이 존재하지 않을때까지 cur를 콘솔에 출력한다.

• 반복문에서 cur은 계속해서 앞의 원소로 교체된다.

3-8. 연결 리스트 역순으로 바꾸기

class SinglyLinkedList {
  // ...
  reverse() {
    let head = this.head;
    let rear = this.rear;

    this.head = rear;
    this.rear = head;

    let prev = this.rear;
    let cur = this.rear.next;
    let count = 0;

    while (count < this.size - 1) {
      const temp = cur.next;
      cur.next = prev;
      cur = temp;
      prev = cur;

      count += 1;
    }

    this.rear.next = null;

    return this;
  }
}

---

4. 시간 복잡도

Insertion	Removal	Searching	Access
O(1)	O(1) or O(n)	O(n)	O(n)

단, 중간 삽입은 O(n)의 시간 복잡도를 가진다.

---

5. Conclusion

연결 리스트(Linked List)를 자바스크립트로 구현하는 연습을 하였다. 구현을 하면서 배열의 메서드도 공부했던 과정처럼 만들어지는 것 같았다. while 문을 언제까지 실행하는 것을 정하는 것이 조금 까다로웠지만 구현을 하고 나니 많은 공부가 되었다. 블로그를 참고하였는데 참고하면서 최대한 의미를 파악하고 나의 방식으로 다시 코드를 구현하도록 노력했다. 연결 리스트가 앞으로 얼마나 많이 사용할지는 모르겠지만 오늘 배운 내용이 자료 구조를 공부할 때 많은 도움이 되었으면 한다. 연결 리스트는 다른 자료 구조를 구현하는데 많이 사용하기 때문에 기본이라고 생각한다. 머리가 살짝 지끈거리다.🤣

---

출처

위키백과 - 연결 리스트 Javascript를 이용한 Linked List 구현

---

📅 2022-09-01