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

단순 연결 리스트란?

연결리스트는 데이터를 저장하는 자료구조 중 하나이다.

연결리스트 종류도 여러개 있지만, 지금 살펴보려는 것은 단순 연결 리스트이다.

 

연결리스트는 여러 개의 노드(Node)로 이루어져 있다. 단순 연결 리스트는 2개의 필드를 가지고 있는데, 데이터 필드와 다음 노드 주소를 가지고 있는 링크 필드(포인터)로 구성되어 있다.

 

create, search, insert, remove 등을 효율적으로 구현하기 위해 사용한다고 한다.

 

구현 코드

전체적인 구현 코드는 다음과 같다.

class LinkedList {
  constructor() {
    let init = new Node("init");
    this.head = init;
    this.tail = init;

    this.currentNode = undefined;
    this.dataCount = 0;
  }

  length() {
    return this.dataCount;
  }

  append(data) {
    let newNode = new Node(data);

    this.tail.next = newNode;
    this.tail = newNode;
    this.dataCount += 1;
  }

  toString() {
    let currentNode = this.head;
    currentNode = currentNode.next;

    let s = "";
    for (let i = 0; i < this.dataCount; i++) {
      s += `${currentNode.data}, `;
      currentNode = currentNode.next;
    }
    return `[${s.slice(0, -2)}]`;
  }

  insert(index, data) {
    let currentNode = this.head;
    currentNode = currentNode.next;

    for (let i = 0; i < index - 1; i++) {
      currentNode = currentNode.next;
    }

    let newNode = new Node(data);

    newNode.next = currentNode.next;
    currentNode.next = newNode;

    this.dataCount += 1;
  }
}

l = new LinkedList();
l.append(1);
l.append(2);
l.append(3);
l.append(10);
l.append(20);
l.append(30);
l.insert(2, 1000);
console.log(l.length());
console.log(l.toString());

 

코드를 기능별로 나눠서 설명해보면 다음과 같다.

 

Node 클래스

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

Node 클래스는 연결리스트의 각 노드를 생성하는 역할을 한다.

생성자(constructor) 메서드에서는 데이터를 매개변수로 받아 노드를 초기화한다.

각 노드는 데이터와 다음 노드를 가리키는 next 포인터를 가지고 있다.

 

LinkedList 클래스

class LinkedList {
  constructor() {
    let init = new Node("init");
    this.head = init;
    this.tail = init;
    this.currentNode = undefined;
    this.dataCount = 0;
  }

...

LinkedList 클래스는 연결리스트를 구현하는 역할을 한다.

생성자(constructor) 메서드에서는 초기 상태의 연결리스트를 설정한다.

init이라는 이름의 노드를 생성하여 head와 tail로 설정한다. 또한, currentNode는 초기값으로 undefined를 할당하고, dataCount는 초기값으로 0을 할당한다.

 

length() 메서드

  length() {
    return this.dataCount;
  }

length() 메서드는 연결리스트의 데이터 개수인 dataCount를 반환한다.

 

append() 메서드

  append(data) {
    let newNode = new Node(data);
    this.tail.next = newNode;
    this.tail = newNode;
    this.dataCount += 1;
  }

append(data) 메서드는 연결리스트의 끝에 새로운 데이터를 추가한다.

새로운 데이터를 가지는 Node 객체인 newNode를 생성한 후, 현재 tail이 가리키는 노드의 next 포인터를 newNode로 설정한다. 그리고 tail을 newNode로 업데이트하고, 데이터를 추가했으니 dataCount를 1 증가시킨다.

 

toString() 메서드

 toString() {
    let currentNode = this.head;
    currentNode = currentNode.next;
    let s = "";
    for (let i = 0; i < this.dataCount; i++) {
      s += `${currentNode.data}, `;
      currentNode = currentNode.next;
    }
    return `[${s.slice(0, -2)}]`;
  }

toString() 메서드는 연결리스트의 데이터를 배열 형태로 반환한다.

현재 노드를 가리키는 currentNode 변수를 사용하여 순회하면서 각 노드의 데이터를 배열로 연결한다.

마지막으로 배열 형태로 반환하기 위해 [ ]로 감싼다. slice에서 마지막 인자를 -2로 설정했는데, 이는 마지막 ", "를 제거하기 위해서다. 

 

insert() 메서드

  insert(index, data) {
    let currentNode = this.head;
    currentNode = currentNode.next;
    for (let i = 0; i < index - 1; i++) {
      currentNode = currentNode.next;
    }
    let newNode = new Node(data);
    newNode.next = currentNode.next;
    currentNode.next = newNode;
    this.dataCount += 1;
  }
}

insert(index, data) 메서드는 주어진 인덱스에 데이터를 삽입한다.

currentNode 변수를 사용하여 인덱스에 해당하는 위치로 이동한 후, 주어진 데이터를 가지는 새로운 노드를 생성하여 연결리스트에 삽입한다. 삽입 과정에서 dataCount를 1 증가시킨다.

 

연결리스트 생성 및 조작

let l = new LinkedList();
l.append(1);
l.append(2);
l.append(3);
l.append(10);
l.append(20);
l.append(30);
l.insert(2, 1000);
console.log(l.length()); // 출력: 7
console.log(l.toString()); // 출력: [1, 2, 1000, 3, 10, 20, 30]

LinkedList 클래스의 객체를 생성한 후 데이터를 넣어본 코드이다.

 

마무리

지금까지 연결리스트에 대해 알아보았다.

사실 아직 완전히 이해가 되지는 않아서 관련된 자료구조 구현 문제를 풀면서 적용해보는 연습을 해야할 것 같다.

또한 그러한 상태에서 글을 작성해서 부족한 점이 느껴진다. 삭제하는 경우는 구현하지 못했는데 추후 추가 및 수정하며 글을 보완해야겠다.

 

아래 링크를 통해 연결리스트에 대해 연습할 수 있다.

Linked List (Single, Doubly), Stack, Queue, Deque - VisuAlgo

 

 

 

참고: 제주코딩베이스캠프 강좌,456+