Linked List

코공·2020년 12월 5일

JavaScript

Linked List란?

의미

각 데이터들을 한 줄로 연결시킨 모양을 띄우고 있는 자료 구조.
크기가 동적인 자료구조로, 자료구조를 구성하는 요소.
등이라고 설명할 수 있다. 사실 글로 보면 진짜 무슨 말인지 1도 모름. 그림이 편하다.

내 기준 : 각 데이터를 "노드"에 담아서 노드끼리 연결하여 데이터를 저장하는 구조.

그럼 노드란 무엇인가?

요 그림처럼 지우개처럼 생긴 것을 node라고 한다.
node에는 2가지 부분이 있다. Data(우리가 넣을 값)을 담는 부분과 Next부분.
Next는 다음 노드와 연결을 시켜준다. 만약, B부분에 DATA가 없으면
next는 null이 된다.

처음에 노드가 어떻게 생겼는지 몰라서 linked list를 이해하는데 엄청 오래걸렸다..

Linked List의 특징

위의 노드는 1개당 4 byte 메모리를 차지하며, 더블 링크드일 경우엔 노드 하나에 8 byte의 링크 메모리를 차지한다. (더블 링크드는 나중에 다시 배워보자.)
배열에 비해 데이터의 추가 및 삽입이 용이하다. (배열과 비교가 많이 된다.)
배열보다 메모리를 효율적으로 쓸 수 있다.
특정 위치의 데이터를 검색하기 위해서는 처음부터 끝까지 순회해야 하기 때문에 탐색에 비효율적임.
head / next / tail 로 구분할 수 있다.

head: {0: 'apple', next: {1: 'banana', next: {2: 'dream', next: null}}}}
tail: {2: 'dream', next: null}
1. 0번째 노드의 값은 'apple' //
2. 그리고 1번째 값인 'banana'가 있으니까 apple의 next는 'banana'가 된다.  //
3. 2번째 값인 'dream'의 next는 더 이상 없기에 Next === null//
4. 그러면 'dream'이 마지막 데이터이기 때문에 tail이다.

Linked list의 메소드

addToTail(value): 연결 리스트의 마지막에 데이터를 추가합니다.

getNodeAt(index): 인덱스를 넣었을 때, 그 인덱스가 어떠한 값을 가지고 있는지 반환합니다.

contains(value): 해당 값이 연결 리스트에 있는지 true와 false로 반환합니다.

indexOf(value): 해당 값이 어떤 인덱스에 있는지, 인덱스 값과 -1로 반환합니다.

remove(value): 해당하는 연결 리스트의 값을 지웁니다.

size(): 연결 리스트의 사이즈를 반환합니다.

Linked list 코드

1. 기본 코드

일단 노드와 Linked lisk의 뼈대를 만드는 코드이다.
this.next는 기본적으로 Null이고, 여기다가 데이터를 추가할 예정!

2. 노드 추가

처음에는 온통 = node = node =node라서 이해가 가지 않았따.
하지만, 이제 우리는 node의 모습, 즉 외형이 어떻게 생겼는지 알고 있다.
데이터를 넣기 위해서는 Node가 있어야 한다. 그래서 head와 tail을 node로 만들어 주는 것!
자세히 보자!

⭐️데이터를 'A' 1개만 넣었을 때.

2번 째 데이터가 없으니 next = null이 된다.

head: {0: 'A', next: null}

⭐️데이터를 'B'도 넣어, 총 2개가 될 때.

head: {0: 'A', next: {1: 'B', next:null}}

Linked list는 뒤에서부터 데이터를 넣어주어야 한다 !
그래서 코드에서 this.tail.next에 데이터를 넣은 것!

위의 행동이 계속 반복된다.

3. 노드 삭제

Linked list에서 노드를 삭제를 하기 위해서는 조금 특별한 방법이 필요하다.
linked list에서 데이터 삭제는 링크를 끊어 버리는 것.

위의 그림처럼. A의 next를 b가 아니라 c로 연결해주면, b는 자연스럽게 삭제가 된다.
요 그림과 같은 코드를 만들면 가능!

만약 우리가 위의 그림에서 'B'를 삭제하고 싶다면?
1. this.head.value === value를 통해 this.head === 'B'를 찾았다.
2. this.head = this.head.next로 바꿔준다.
=> 요 건 'B'를 'B'의 next인 'C'로 값을 바꿔 준다는 것.
3. 그러면 원래 'A'의 next는 'B' 였지만, 2번을 통해 'A'의 next는 'C'가 된다.
4. 'A'는 next 링크를 통해 'C'와 연결이 되면서, 자연스럽게 'B'는 아무와 연결이 되어있지 않아 사라지게 된다....