[Typescript] 자료구조 : 단방향 연결 리스트 (Singly-LinkedList)

자료구조를 공부할 때, 처음 등장하는 녀석입니다.

연결 리스트. 말 그대로, 데이터 (노드)를 연결해 놓은 것입니다.

 

 

 

단방향 연결 리스트의 모습

 

 

 

단방향 연결 리스트의 특징

• 탐색 시, O(n) 만큼 소요됩니다.
• 추가, 삭제 시, O(1) 만큼 소요됩니다.
• 메모리 상으로 인접하지 않은 데이터들을 연결할 수 있습니다. (공간 효율성이 뛰어남)
• 다음 노드의 위치(next)를 잃어버린다면, 데이터 손실이 일어날 수 있습니다.

 

 

 

배열과의 비교하기

배열의 특징

• 탐색 시, O(1) 만큼 소요됩니다.  (인덱스로 데이터에 접근 가능)
• 추가, 삭제 시, O(n) 만큼 소요됩니다.  (데이터 추가 or 삭제 후, 모든 데이터를 이동시켜야 하기 때문)
• 데이터들이 메모리상으로 인접한 위치에 있습니다.
• 탐색할 일이 많다면 배열, 추가 & 삭제할 일이 많다면 연결 리스트를 사용하는 것이 좋습니다.

 

 

위에서 얘기한 배열은, 크기가 고정된 배열 (정적 배열)을 의미합니다.

자바스크립트에서 사용하는 배열은 크기가 가변하는 동적 배열인데요.

일반적으로 "정적 배열"과 "연결 리스트"를 비교하기 때문에 위와 같이 정리하였습니다.

 

 

 

 

데이터 노드 구현하기

class Node {
    item: number; 
    next: Node | null = null;

    constructor(item: number) {
      this.item = item;
    }
  }

Node 객체는 숫자 데이터와 다음 노드를 기억하도록 했습니다.

 

 

 

 

단방향 연결 리스트 틀 잡기

class linkedList {
    private head: Node = null;
    private length: number = 0;

    traverse() {
    	...
    }

    append(node: Node) {
    	...
    }

    insertAt(idx: number, node: Node) {
    	...
    }

    deleteAt(idx: number) {
    	...
    }

단방향 연결 리스트 객체는 head와 length를 가지고 있습니다.

head는 처음 노드를 length는 노드의 갯수를 의미합니다.

 

 

총 4개의 메소드를 제공하려고 합니다.

첫 번째 노드의 인덱스(idx)를 1로 정했습니다.

• traverse : 연결 리스트를 순회하고, 노드의 데이터를 출력해줍니다.
• append : 연결 리스트 맨 끝에, 새로운 노드를 추가합니다.
• insertAt : 연결 리스트 중간에, 새로운 노드를 추가합니다.
• deleteAt : 연결 리스트 중간의, 특정 노드를 삭제합니다.

 

 

 

traverse, append 메소드 구현

// traverse
traverse() {
  let current = this.head;
  let result = "";

  while (current) {
    result += current.item + " -> ";
    current = current.next;
  }

  result += "null";

  console.log(result);
}

// append
append(node: Node) {
  let current = this.head;

  if (!current) {
    this.head = node;
    this.length += 1;

    return;
  }

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

  current.next = node;
  this.length += 1;
}

 

 

 

 

 

insertAt, deleteAt 메소드 구현

// insertAt
insertAt(idx: number, node: Node) {
  if (idx > this.length) {
    console.log("error!");
    return;
  }

  if (idx === 1) {
    node.next = this.head;
    this.head = node;
    this.length += 1;

    return;
  }

  let prev = null;
  let current = this.head;
  let currentIdx = 1;

  while (current.next && idx !== currentIdx) {
    prev = current;
    current = current.next;
    currentIdx += 1;
  }

  node.next = current;
  prev.next = node;
  this.length += 1;
}


// deleteAt
deleteAt(idx: number) {
  if (idx > this.length) {
    console.log("error!");
    return;
  }

  if (idx === 1) {
    this.head = this.head.next;
    this.length -= 1;

    return;
  }

  let prev = null;
  let current = this.head;
  let currentIdx = 1;

  while (current.next && idx !== currentIdx) {
    prev = current;
    current = current.next;
    currentIdx += 1;
  }

  prev.next = current.next;
  this.length -= 1;
}

 

 

 

 

구현한 코드를 테스트 해보기

// Test
  const list = new linkedList();

  list.append(new Node(1));
  list.append(new Node(2));
  list.append(new Node(3));

  list.traverse();

  // 중간 데이터 제거
  list.deleteAt(2);

  list.traverse();

  // 중간 데이터 삽입
  list.insertAt(2, new Node(4));

  list.traverse();
}

 

console 출력값

// 출력값
1 -> 2 -> 3 -> null
1 -> 3 -> null
1 -> 4 -> 3 -> null