[ Data Structure ] 🔗 연결 리스트(Linked List)

📚 연결 리스트(Linked List)의 개념

연결 리스트(Linked List) 는 데이터를 연속적인 메모리 공간에 저장하는 배열과는 다르게,
각 데이터가 저장된 위치가 서로 떨어져 있는 자료구조이다.
연결 리스트는 각 데이터가 노드(Node)로 구성되어 있으며, 이 노드는 두 가지 정보를 가지고 있다:

데이터: 노드에 저장된 값
다음 노드를 가리키는 포인터(링크): 다음 노드의 메모리 주소

 

🔗 연결 리스트(Linked List)의 특징

• 동적 메모리 할당 : 배열은 크기가 고정되어 있지만, 연결 리스트는 필요에 따라 동적으로 노드를 추가할 수 있다.
• 노드 추가/삭제가 효율적 : 연결 리스트에서는 중간에 노드를 삽입하거나 삭제할 때 전체 구조를 변경하지 않고,
  몇 개의 포인터만 수정하면 되기 때문에 배열보다 효율적이다.

 

⚙️ 연결 리스트(Linked List)의 구조

가장 기본적인 연결 리스트는 단일 연결 리스트(Singly Linked List) 로,
각 노드가 다음 노드를 가리키는 포인터를 가진다.

[데이터 | 다음 노드] -> [데이터 | 다음 노드] -> [데이터 | 다음 노드] -> null

여기서 null 은 마지막 노드를 의미하며, 더 이상 연결된 노드가 없다는 뜻이다.

📝 주요 연산

• 삽입 : 새로운 데이터를 원하는 위치에 추가하는 것.
  첫 번째 위치, 중간 위치, 마지막 위치에 삽입할 수 있다.
• 삭제 : 원하는 위치에 있는 노드를 제거하는 것.
  노드를 삭제할 때는 해당 노드로 가는 링크를 끊고, 이전 노드가 삭제된 노드의 다음 노드를 가리키도록 한다.
• 탐색 : 특정 데이터를 찾기 위해 첫 노드부터 순차적으로 탐색한다.

예시

연결 리스트에 3개의 데이터(1, 2, 3)를 저장한다고 하면 :

[1 | next] -> [2 | next] -> [3 | null]

만약 중간에 4를 추가하고 싶다면, 2와 3 사이에 새로운 노드를 삽입하면 된다 :

[1 | next] -> [2 | next] -> [4 | next] -> [3 | null]

 

✨ 연결 리스트(Linked List)의 동작 구현하기

우선 다음과 같이 하나의 Node 를 추상화 해서 class를 선언해줬다.

• LinkeList.mjs

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

 

Node 의 동작을 테스트하기 위해 각 Node 인스턴스들을 생성 후
node.next 프로퍼티에 다음 순서의 Node를 참조되게 연결한 뒤

node1에 .data 프로퍼티에 접근해 node1의 데이터를 확인 하고
node1.next에 참조시킨 node2의 .data 프로퍼티에 접근해 확인
node1에서 node1.next인 node2에 접근해 node2의 .next 프로퍼티가 참조하는 node3의 .data에 접근해 출력해보았다.

 

• test.mjs

import { Node } from './Node.mjs'

// 1. Node 인스턴스 생성
const node1 = new Node(1);
const node2 = new Node(2);
const node3 = new Node(3);

// 2. 각 Node의 next 프로퍼티에 다음 Node를 참조할 수 있게 연결
node1.next = node2;
node2.next = node3;

// 3. 각 Node의 next 프로퍼티를 타고 연결된 Node를 확인
console.log(node1.data); // 1
console.log(node1.next.data); // 2
console.log(node1.next.next.data); // 3

 

 

위와 같이 각 `Node`가 잘 연결된것을 확인할 수 있다.


그리고 다음과 같이 연결 리스트(Linked List) 를 LinkedList로 추상화해 class로 구현하고
연결 리스트(Linked List)의 동작을 메서드로 각각 구현하였다.

// * 연결 리스트 추상 자료형
// 1. 모든 데이터 출력 -> printAll();
// 2. 모든 데이터 제거 -> clear();
// 3. 원하는 인덱스에 데이터를 삽입 -> insertAt(index, data);
// 4. 마지막 데이터 뒤에 데이터를 삽입 -> insertLast(data);
// 5. 원하는 인덱스에 데이터를 삭제 -> deleteAt(index);
// 6. 마지막 데이터를 제거 -> deleteLast();
// 7. 원하는 인덱스에 있는 데이터 읽기 -> getNodeAt(index);

export class LinkedList {
  constructor(){
    // 연결 리스트의 시작 Node를 가리킨다.
    this.head = null;

    // 총 저장된 Node의 수
    this.count = 0;
  }

  /**
   * 원하는 인덱스에 데이터를 삽입
   * @param {number} index - 삽입할 위치 index
   * @param {any} data - 삽입할 데이터
   */
  insertAt(index, data){    
    // 예외 처리
    if(index > this.count || index < 0) throw new Error('범위를 넘어갔습니다.');

    // 새로운 Node 생성
    let newNode = new Node(data); 

    if(index === 0){ 
      // 리스트의 가장 앞부분에 삽입할 경우

      // 1. 생성된 Node의 next가 head를 가리키도록 설정
      newNode.next = this.head; 
      // 2. 생성된 Node를 head로 설정
      this.head = newNode; 

    }else{ 
      // 앞부분 삽입을 제외한 원하는 인덱스에 삽입할 경우

      // head에서 부터 시작하기 때문에 head로 초기화
      let currentNode = this.head; 

      // 목표 인덱스 바로 전까지 next를 이용해 currentNode를 이동시킨다.
      for(let i=0; i<index -1; i++){
        currentNode = currentNode.next;  
      }

      // 1. 새로운 Node가 currentNode의 next Node를 가리키도록 설정
      newNode.next = currentNode.next;
      // 2. currentNode가 새로운 Node를 가리키도록 설정
      currentNode.next = newNode
    }

    // 새로운 Node가 삽입되었으니 count를 증가
    this.count++;
  }

  /**
   * 모든 데이터 출력
   * @returns {string} - 모든 Node의 data를 하나의 문자열에 담아 반환
   */
  printAll(){
    let currentNode = this.head;
    let text = '['

    while(currentNode){
      text += currentNode.data
      currentNode = currentNode.next;

      if(currentNode) text += ', ';
    }
    text += ']';
    console.log(text);    
    return text;
  }

  /**
   * 모든 데이터 제거
   */
  clear(){
    this.head = null; // head 초기화
    this.count = 0; // count 초기화
  }

  /**
   * 마지막 데이터 뒤에 데이터를 삽입
   * @param {any} data - 삽입할 데이터
   */
  insertLast(data){
    this.insertAt(this.count, data);
  }

  /**
   * 원하는 인덱스에 데이터를 삭제
   * @param {number} index - 제거할 위치 index
   * @return {{data: number, next: {data: number, next: any} | null}} - 제거된 노드의 데이터와 그 다음 노드에 대한 정보.
   */
  deleteAt(index){
    // 예외 처리
    if(index >= this.count || index < 0) throw new Error('제거할 수 없습니다.');

    let currentNode = this.head;

    if(index === 0){
      // 리스트의 가장 앞부분에 제거할 경우

      // 반환하기 위해 삭제된 Node를 저장
      const deleteNode = this.head;
      // head를 다음 Node인 head.next로 설정
      this.head = this.head.next;
      // 제거했으므로 count를 내린다.
      this.count--;

      // 삭제한 Node 반환
      return deleteNode;

    }else{
      // 리스트의 가장 앞부분을 제외한 위치를 제거할 경우

      // 제거할 Node 이전 Node까지 순회해 제거할 Node의 이전 Node를 가리키게 한다.
      for(let i=0; i<index -1; i++){
        currentNode = currentNode.next;
      }

      // currentNode.next가 참조하고 있는 다음 Node 즉, 제거해야 할 Node를 저장
      let deleteNode = currentNode.next; 

      // 제거할 Node의 next Node를 가리키게 한다.
      currentNode.next = currentNode.next.next;

      // 제거했으므로 count를 내린다.
      this.count--;

      // 삭제한 Node 반환
      return deleteNode;      
    }
  }

  /**
   * 마지막 데이터를 제거
   * @return {{data: number, next: {data: number, next: any} | null}} - 제거된 노드의 데이터와 그 다음 노드에 대한 정보.
   */
  deleteLast(){
    return this.deleteAt(this.count - 1);
  }

  /**
   * 원하는 인덱스에 있는 데이터 읽기 
   * @param {number} index - 읽고자하는 Node의 index
   * @return {{data: number, next: any}} - 해당 Node 반환
   */
  getNodeAt(index){
    // 예외 처리
    if(index >= this.count || index < 0) throw new Error('범위를 넘어갔습니다.');

    let currentNode = this.head;

    // currentNode가 해당 index까지 순회한다.
    for(let i=0; i< index ; i++){
      currentNode = currentNode.next;
    }

    // 최종적으로 이동한 Node를 반환
    return currentNode;
  }
}

 

 

연결 리스트(Linked List) 의 추상 자료형을 정의하고, 이걸 바탕으로 구현한 뒤 각 동작을 테스트해보았다.

• test.mjs

import { Node, LinkedList } from './LinikedList.mjs'

const list = new LinkedList();

console.log('===== insertAt() 다섯 번 호출 =====');

list.insertAt(0,0); // 0번째 위치에 데이터 0 삽입
list.insertAt(1,1); // 1번째 위치에 데이터 1 삽입
list.insertAt(2,2); // 2번째 위치에 데이터 2 삽입
list.insertAt(3,3); // 3번째 위치에 데이터 3 삽입
list.insertAt(4,4); // 4번째 위치에 데이터 4 삽입

list.printAll(); // 데이터 리스트 출력 -> "[0, 1, 2, 3, 4]"

console.log('===== clear() 호출 =====');

list.clear(); // 모든 데이터 제거
list.printAll(); // 데이터 리스트 출력 -> "[]"

console.log('===== insertLast() 호출 =====');

list.insertLast(0); // 마지막 데이터 뒤에 데이터 0을 삽입
list.insertLast(1); // 마지막 데이터 뒤에 데이터 1을 삽입
list.insertLast(2); // 마지막 데이터 뒤에 데이터 2을 삽입

list.printAll(); // 데이터 리스트 출력 -> "[0, 1, 2]"

console.log('===== deleteAt() 호출 =====');
list.deleteAt(0); // 0번째 index 제거
list.printAll(); // 데이터 리스트 출력, "[1, 2]"

list.deleteAt(1); // 0번째 index 제거
list.printAll(); // 데이터 리스트 출력, "[1]"

console.log('===== deleteLast() 호출 =====');
list.insertLast(5); // 마지막 데이터 뒤에 데이터 5을 삽입, "[1, 5]"

list.deleteLast(); // 마지막 데이터를 제거
list.deleteLast(); // 마지막 데이터를 제거

list.printAll(); // 데이터 리스트 출력 -> "[]"

console.log('===== getNodeAt() 호출 =====');

list.insertLast(1); // 마지막 데이터 뒤에 데이터 1을 삽입
list.insertLast(2); // 마지막 데이터 뒤에 데이터 2을 삽입
list.insertLast(3); // 마지막 데이터 뒤에 데이터 3을 삽입
list.insertLast(4); // 마지막 데이터 뒤에 데이터 4을 삽입
list.insertLast(5); // 마지막 데이터 뒤에 데이터 5을 삽입, "[1, 2, 3, 4, 5]"

const secondNode = list.getNodeAt(2); // 2번째 인덱스에 있는 데이터 읽기

console.log(secondNode); // Node { data: 3, next: Node { data: 4, next: Node { data: 5, next: null } }}

 

장점

메모리 공간을 효율적으로 사용 가능.
크기가 유동적이므로 데이터를 많이 추가/삭제할 수 있음.
삽입과 삭제가 배열보다 효율적.

단점

특정 위치의 데이터를 찾기 위해서는 처음부터 차례대로 탐색해야 하므로 접근 속도가 느림.
노드마다 포인터를 저장해야 하므로 추가적인 메모리 사용이 발생함.
이렇게 연결 리스트는 배열과 달리 데이터의 삽입/삭제가 빈번한 상황에서 매우 유용하게 쓰이는 자료구조다.

---