자바스크립트 12. 자료구조(Data Structure) - 연결리스트(Linked List)

자료구조 3번째 연결 리스트를 기록해보자!

Photo by JJ Ying on Unsplash

📕연결리스트(Linked List) 개념

연결리스트(Linked List)는 영문 뜻 그대로 연결되어 있는 목록을 말한다. 각 데이터들을 하나의 줄로 연결되어 있는 모양을 하고 있는 구조이다. 각각의 데이터들은 링크로 연결이 되어 있다. 

 

연결리스트에는 노드(Node)가 있다. 이 노드 하나하나에는 데이터와 다음 노드를 가르키는 링크가 들어있다. 링크가 반드시 있어야 다음 연결되어 있는 데이터를 찾을 수 있다. 그리고 한 공간에 있지만 분리되어서 있다. 다음 그림을 보면 이해가 쉬울 것 같다.

노란색 상자는 각각의 노드를 표현해주고 있고, 분리되어 있는 두개의 방안에는 각각 그 노드가 가지는 데이터와 다음 노드의 위치를 알려주는 링크가 들어있다. 첫번째 노드는 head이고 마지막 노드는 tail이다. 그래서 연결리스트의 경우에는 내가 원하는 데이터를 찾기 위해서는 반드시 head에서 부터 하나씩 다음 노드로 넘어가면서 찾게 된다.

---

📍연결리스트 메소드

이번 코드스테이츠 스프린트에서 연결리스트 메소드를 구현한 것은 총5가지 이다.

• addToTail(value) - 주어진 값을 연결리스트의 끝에 추가합니다.

• remove(value) - 주어진 값을 찾아서 연결을 해제(삭제)합니다.

• getNodeAt(index) - 주어진 인덱스의 노드를 찾아서 반환합니다. 값이 아니라 노드를 반환해야 하는 것에 주의해햐합니다. 해당 인덱스 노드가 없다면 undefined를 반환합니다.

• contains(value) - 연결리스트에 주어진 값을 가지는 노드의 존재여부를 반환합니다.

• indexOf(value) - 주어진 값의 인덱스를 반환합니다. 없을 경우 -1을 반환합니다.

---

💻연결리스트 메소드 구현

스프린트에서 연결리스트 메소드 구현은 클래스로 구현해 주었다.

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

class LinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this._size = 0;
  }

1. addToTail(value)

- head가 있는 경우와 없는 경우로 나누어서 작성

- 새로운 노드를 new키워드를 활용해서 만들었다.

- head가 없는 경우에는 새로운 노드가 처음으로 시작되는 값이자 마지막 값이 되기 때문에 head와 tail에 각각 지정

- head가 있는 경우라면 tail에 새로 연결해주고, 현재tail의 다음 링크 주소에 새로운 노드를 주었고, tail에 새로운 노드를 지정해 준다.

 

2.remove(value)

- 주어진 value가 있는지 확인 하기 위해서는 반드시 head에서 부터 시작해서 연결된 주소를 타면서 확인을 해야한다.

- 현재 노드를 최초에 head로지정해준다.

- while을 활용하고, 현재노드를 다음노드로 계속 확인하도록 한줄 작성한다.

- 노드의 value값이 주어진 value와 같다면 삭제를 해준다(?)

 

🖐🏻잠깐만! 연결리스트에서는 삭제를 어떻게 할까? 다음 사진을 보자!

가비지 컬렉터는 저런 모습이 아닙니다. 오해하지 마시길.....

이 그림을 통해서 어떻게 삭제되는지 살펴보자. 만약에 Node3을 삭제를 하고 싶은 경우에, 먼저 Node2를 Node4로 연결을 시켜 주게되면, Node3는 그럼 광활한 데이터 세상을 떠도는 것이 아니라, 가비지 컬렉션(garbage collection)을 수행하는 가비지 컬렉터(garbage collector)에 의해서 사라지게 된다.

 

가비지 컬렉션이란 말그대로 쓰레기, 불필요한 객체입니다. 이 객체는 필요하지도 않고, 쓰이지도 않고 있는데 메모리를 점유하고 있기때문에 해제켜주어야 한다. 아니면 다시 사용 가능한 자원으로 회수하기도 한다. 이때 자동으로 프로그램이 실행되어 쓸데없는 메모리들을 알아서 수집관리 해준다.

 

3. getNodeAt(index)

- 마찬가지로 연결리스트를 순회하기 위해서, 현재노드를 head로 설정 하고 반복문을 설정해 준다.

- 그리고 해당하는 index의 값을 찾아 주기 위해서, 돌면서 카운트를 해주는 변수를 선언해준다. 변수는 돌때 마다 1씩 커진다.

- 돌면서 해당하는 index와 변수가 같아질 때, 해당하는 노드를 반환한다.

 

4. contains(value)

- 마찬가지로 연결리스트를 순회하기 위해서, 현재노드를 head로 설정 하고 반복문을 설정해 준다.

- 반복문을 돌면서 해당하는 값과 일치하는 노드의 값이 나오면 true를 반환, 아니면 false를 반환한다.

 

5. indexOf(value)

- 마찬가지로 연결리스트를 순회하기 위해서, 현재노드를 head로 설정 하고 반복문을 설정해 준다.

- getNodeAt과는 다르게 이번에는 index를 구하는 메소드이다. 상당히 유사하다. 짱구를 조금만 굴리면 된다.

 

다음에도 자료구조를 기록해보자!