목차
- linked list란?
- linked list의 구조
- 배열과의 차이
- pseudo code
1. Linked list란?
음악을 듣다보면 되감기이나 다음 트렉 버튼을 볼 수 있습니다.
이 기능이 작동할 수 있는 이유는 각 버튼에 이전, 혹은 다음 곡들의 요소가 서로 연결되어있기 때문입니다.
이렇게 요소들이 일정한 방향을 기준으로 서로 연결되어있는 자료구조가 linked list입니다.
2. Linked list의 구조
(여기서는 singly-Linked list를 설명합니다.)
Linked list는 노드(node)로 구성되어있습니다.
노드에는 value과 next값이 존재합니다. 그 중에서는 next에는 다음 node의 값이 할당되면서 다음 노드와 현재 노드가 연결되게 됩니다.
(출처 : https://www.softwaretestinghelp.com/linked-list/)
가장 앞의 node는 head이며 가장 마지막 node(next값이 null)는 tail이 됩니다.
3. 배열과의 차이
1) 배열
배열은 원래는 처음 선언할 때 크기를 고정해야 합니다 (변경이 불가능)
=> 그래서 배열은 정적 구조라고 합니다.
자바스크립트에서 배열의 크기가 변하는 이유는 자바스크립트가 사기라서...
배열에서는 요소를 추가하기 위해서는 요소 뒤의 요소를 모두 뒤로 이동해야 합니다.
요소를 제거하기 위해서는 제거 후에 요소를 전부 앞으로 이동해야 합니다.
따라서 제거와 추가에 매우 비효율적입니다.
대신 index값만 가지고 있으면 자료추적이 매우 빠릅니다.
ex) arr[0] , arr[3]
2) Linked list
반면에 Linked list는 node만 추가하면 크기는 계속 변할 수 있으므로 동적 구조라고 불립니다.
노드를 추가하기 위해서는 원하는 위치 이전 노드와 다음 노드 사이에 추가를 하고 서로를 연결하면 됩니다.
제거하기 위해서는 이전 노드와 다음 노드만 서로 연결해주면 해당 노드는 연결점이 없어져서 제거가 됩니다.
=>노드 제거 원리
(출처 : https://stackoverflow.com/questions/41474163/singly-linked-list-remove)
반면에 자료를 참조하기 위해서는 head부터 next를 통해 추적해야 하므로 자료를 찾는 속도가 매우 느리다.
=> 한 장 요약
(출처 : https://opentutorials.org/module/1335/8636)
4. pseudo code
Linked-list는 노드로 구성되어있다.
//노드 생성하는 함수
function Node(value) {
this.data = value;
this.next = null;
};또한 Linked-list는 head와 tail이 존재한다
function LinkedList() {
this._size = 0;
this.head = null;
this.tail = null;
};- 새로운 노드 추가
1) 만약 head가 없을 경우( null)
head와 tail은 새로운 노드가 된다.
2) head가 존재하는 경우
tail.next와 tail에 노드를 할당합니다.
여기에 size를 하나씩 추가한다.
LinkedList.prototype.addToTail = function(value){
let node = new Node(value);
if(!this.head) {
this.head = node;
this.tail = node;
} else {
this.tail.next = node;
this.tail = node;
}
this._size++;
return node;
}- 노드 제거
1) 제거할 노드가 존재하지 않다면
undefined를 리턴
2)제거할 노드가 head인 경우
head를 head.next에 할당하여 head를 제거
3)그 이외
처음 노드를 정의(preNode) => head의 노드
처음 노드의 next를 정의(nextNode) => head의 next 노드
nextNode의 value가 찾으려는 노드의 value와 일치할때까지
preNode와 nextNode를 하나씩 전진
만약 일치한다면!
preNode.next = nextNode.next를 통해서 nextNode를 삭제(nextNode가 없애줄 값이므로)
이때 사이즈는 1개 줄여준다.
LinkedList.prototype.remove = function(data){
if(!this.head) {
return undefined;
}
if (this.head.data === data) {
this.head = this.head.next;
return this;
}
let preNode = this.head;
let nextNode = this.head.next;
while(preNode) {
if(nextNode.data === data) {
break;
}
preNode = nextNode;
nextNode = nextNode.next;
}
preNode.next = nextNode.next;
this._size--;
return this;
}- array처럼 index를 매개변수를 이용해서 value 찾기
1)index가 size보다 클 때
undefined를 리턴한다
2)그 이외
index만큼 head에서부터 next를 통해 전진한 후 결과값을 리턴
LinkedList.prototype.getValue = function(index){
let result = this.head;
if(index > this._size) {
return undefined;
}
for(let i = 0; i < index; i++) {
result = result.next;
}
return result;
}- 값이 존재하는 지 여부
head부터 next를 통해 value를 추적
value를 찾았을 경우 true
value가 없다면 false
Linkedlist.prototype.contains = function(value){
let result = this.head;
while(result){
if(result.value === value){
return true;
}
result = result.next;
}
return false;
};- 위치를 추적
head부터 next를 통해 value를 추적
count를 지정 (기본값 = 0)
next로 재할당할때마다 count를 1 추가
value를 찾았을 경우 count를 리턴
value가 없다면 -1를 리턴
LinkedList.prototype.indexof = function(value){
let result = this.head;
let count = 0;
while(result){
if(result.value === value){
return count;
}
result = result.next;
count++;
}
return -1;
};- Linked list의 크기
size를 리턴하면 된다.
LinkedList.prototype.size = function(){
return this._size;
};