Linked List(연결리스트) 의 개념과 구현

Linked List(연결 리스트) 

Linked List의 자료구조 (출처: 본인 제작)

 

  Linked List(연결 리스트)는 크기가 '동적'인 자료구조로서, Node(노드)의 연결로 이루어졌습니다.

여기까지는 배열과 유사해 보일 수 있습니다. 대신 배열과의 차이점이 있습니다. 바로 특정한 인덱스를 가지고 있지 않다는 것이지요. 대신, 포인터를 통해 각각의 노드를 연결짓고 있습니다. 그렇기 때문에 배열의 경우, 특정 인덱스를 통해 해당 인덱스의 값을 호출할 수 있지만 연결 리스트(Linked List)의 경우는 특정 노드를 확인하기 위해서는 전체 연결 리스트를 훑어야만 합니다. 포인터를 가지고 있기에 특이한 점은 첫 노드를 삭제하면 다음을 가리키는 포인터가 사라지므로, 연결이 끊어져 연결 리스트 자체가 삭제되게 됩니다. 마치 뱀의 머리를 자르면 뱀이 죽어버리는 것(?)과 비슷한 형태입니다.

 

Why Linked List?

그렇다면 연결 리스트는 왜 사용하게 된 것일까요? 배열과 유사하고, 더 나은 장점도 없는 것 같은데 말이죠. 그 이유는 컴퓨터 언어의 초창기 시절에 있습니다. 당시 C의 내장 배열은 배열에 포함될 수있는 항목 수와 해당 메모리 양도 지정해야만 했습니다. 데이터를 추가하거나, 삭제할 때마다 변경된 메모리를 수정하는 것은 어려웠고, 항상 메모리 문제를 고민해야 했습니다. 즉, 이 메모리 문제를 해결하고자 연결리스트가 만들어지게 된 것이지요.

현재의 JasvaScript의 Array는 이런 장점이 잘 구현된 형태이긴 하지만 연결 리스트의 구조를 익히는 것이 기존에 연결 리스트로 구성된 데이터를 이해하는데 도움이 됩니다.

 

참고 링크 : www.notion.so/Data-Structure_Part-2-Linked-List-4808a51bdd77416a9dd14a3e28710e0c#7d5ff05d24a04d4a9201ab57efffe9ea

 

장점과 단점

가장 큰 단점은 특정 인덱스에 도달하기 위해 전체 리스트를 순회해야한다는 점입니다. 그렇기 때문에 해당 작업을 위해서는 O(n)의 시간 복잡성을 갖습니다.

 

실제 활용

• 방문한 웹 페이지 리스트

• 실제 stack이나 queue를 구성되는데도 linked list를 활용한 것

• 음악 스트리밍 목록

• 간단한 계산기를 만드는 데도 활용할 수 있음

  참고 : https://levelup.gitconnected.com/the-linked-list-data-structure-6559a1e15f09

 

---

 

Implementation of LinkedList in Javascript_메소드

1. add(element)  
   • 리스트의 끝에 새로운 요소를 추가함. 
2. insertAt(element, index)
   • 주어진 인덱스에 요소를 추가함
3. removeFrom(index)
   • 특정 인덱스의 요소를 삭제하고 반환함.
4. indexOf(element) – 주어진 element를 가진 인덱스를 반환
5. size_of_list() – 말 그대로 list의 크기를 반환

출처 : https://www.geeksforgeeks.org/implementation-linkedlist-javascript/

 

Singly Liked List 구현

Singly는 Doubly와 달리 단방향으로만 이동이 가능하다. 그렇기 때문에 element를 추가하면 아래와 같은 형태로 구상하였다.

참고로 기본 형태는 객체이다.

 

node 1개 : [head] → node ←[tail] head와 tail 모두 node를 가리킴

node 2개 : [head] → node 1 -(next)→node 2 ←[tail]

node 3개 : [head] → node 1 -(next)→node 2 -(next)→node 3←[tail]

의 형태로 진행된다. 즉 haed 포인터는 제일 앞에 고정되고, 모든 데이터들이 haed에 담겨있다. 이 데이터들은 next를 이용해서만 연결되는 구조이다.

 

좀더 실질적으로 표현을 해보자면

• 첫 LinkedList 실행 : LinkedList {head: null, tail: null, _size: 0}

• 노드 두개 추가 : {head: Node, tail: Node, _size: 2}

이런식으로 객체 안에 객체가 있는 모습이다.

 

 

 

---

 

메소드 구현하기

구현해야 하는 메소드는 다음과 같다.

 

addToTail 메소드

: 주어진 값을 연결 리스트의 끝에 추가

1. 새로운 노드(Node객체)를 만드는 변수(node) 선언

2. 노드 전체가 비어있다면(= head가 비어 있다면)

   2-1. head에 새 노드 추가. tail도 새 노드 바라보기

3. 노드에 값이 있다면

   3-1. head.next 값이 존재할 때까지 들어가서(while문 사용)

   3-2. head.next에 새 노드 할당하기(모든 노드는 결국 head 안에 있으므로)

   3-3. tail.next에도 새 노드 할당하기

   3-4. tail 자체도 새 노드 바라보게 하기(tail 재 정의)

4. this._size 1 증가

 

remove 메소드

: 주어진 값을 찾아서 연결을 해제(삭제)

파라미터 : value(노드 아님)

전제)

1. linked list는 반드시 전체를 순회하기 때문에 해당 값의 인덱스를 탐색할 수 있어야 함.

2. 1번의 기능을 doubly linked list에서는 두개의 포인터를 이용해서 탐색하지만 singly에서는 추가로 구현을 해야 함.

3. 이전 데이터를 가리킬 수 있는 임의의 포인터를 선언(prev)하고 null 할당

4. head가 끝날때까지(while 문 이용) 탐색하면서

   2-1. prev는 탐색하고 있는 현재 포인트를 가리키기

   2-2. head는 head.next를 할당하면서 다음 데이터를 탐색하게 하기

5. 탐색한 값prev이 주어진 값(value)과 같을 때

   3-1. head의 값과 같을 때 : head를 head.next를 가리키게 하기

   3-2. head가 아니면 : 탐색한 값의 next가 head.next가 되게 하기

6. this.size 1 감소

7. head.value 반환

**개인적으로 구현할 때는 singly 임에도 이전 데이터의 내용이 필요해서 prev라는 인자를 선언하였다.

 

 

getNodeAt 메소드

: 주어진 인덱스의 노드를 찾아서 반환. 값이 아니라 노드를 반환해야 함.

: 해당 인덱스에 노드가 없다면 undefined를 반환

파라미터 : index, 반환 값 : 노드

1. count할 변수 선언
2. head가 없을 때까지(while 문 사용)
3. count 1씩 증가, head는 head.next를 향하게 하여 계속 탐색
4. 만약 count가 index랑 같다면 count 반환
5. 해당 인덱스가 없다면 undefined 반환

 

contains 메소드

: 연결리스트에 주어진 값을 가지는 노드의 존재 여부를 반환(boolean)

파라미터 : value, 반환값 : true/false

1. head가 존재할 때까지 탐색하기 : 계속해서 head는 head.next를 바라보게 하기
2. 탐색 중인 값이 주어진 value와 같을 때 : true
3. 아니면 false

 

indexOf 메소드

: 주어진 값의 인덱스를 반환합니다. 없을 경우 -1을 반환

1. count 할 변수 선언
2. head가 없을 때까지 탐색하면서 count 1씩 증가
3. 주어진 value와 탐색값이 같을 때 : count 반환
4. 주어진 값이 없을 경우 -1 반환

 

size 메소드

: 속성으로 설정된 this._size 반환

 

 

공통적으로 포인트라고 느껴졌던 부분은

while 문 안에서 current = current.next를 지정해 주어야 한다는 점이었다. 왜냐하면 head 안에서 다음 데이터(next가 바라보는 데이터)를 계속해서 확인하는 작업이 있어야 탐색이 가능하기 때문이다. 이는 포인터로만 연결된 linked list의 탐색 특성이기도 하다.

 

 

---

생각해볼 질문

• 노드는 어떻게 구성되어 있나?

  : 선형구조(linear fashion)로 각각의 노드(node; data를 의미함)가 포인터로 연결되어 있음.

  : JS에서는 array와 유사한 형태를 보임

• 연결 리스트의 종류는?

  1. 단일 연결 리스트 : https://humanwhocodes.com/blog/2019/01/computer-science-in-javascript-linked-list/
  포인터 : 1개. 다음 노드를 가리킴
  
  2. 이중 연결 리스트 : https://humanwhocodes.com/blog/2019/02/computer-science-in-javascript-doubly-linked-lists/

  포인터 : 2개. 이전의 노드와 다음 노드를 각각 가리킴

  ⇒ 단일 연결 리스트와 달리 한 방향으로 가지 않고 반대 방향으로도 확인할 수 있음.