Linked List
사전적 의미의 Linked List
Linked
1.형용사 유전 <유전자가> 연쇄된, 연계된
연계되어있는 데이터의 List이다.
맛있겠다 줄줄이 소세지..
소세지 하나하나가 데이터이고 서로를 연결하고있는 부분을 링크라고 생각한다면 어떨까 한다.
연결 리스트는 그 크기가 동적인 자료구조로, 자료구조를 구성하는 요소, -우리는 이것을 노드(Node) 라고 부릅니다- 노드의 연결로 이루어진 자료 구조입니다
참고 : https://towardsdatascience.com/8-common-data-structures-every-programmer-must-know-171acf6a1a42
배열과 Linked List의 장단점
배열
메모리를 연속적으로 할당한다.
동일한 데이터 타입을 연속적으로 저장할 수 있다.탐색이 쉽다
고정된 크기를 가지고 있어서 배열의 처음이나 중간에 원소를 넣고 빼기 어렵다.
탐색/정렬에 용이
Linked List
메모리상에 원소들이 연속적으로 위치하지 않는다.
배열에 비해 데이터의 추가/사입이 용이하다.
배열에 비해 메모리를 더 효율적으로 쓸 수 있다.
특정 위치의 데이터를 검색하기 위해서는 처음부터 끝까지 순회해야 한다
추가/삭제에 용이
노드(Node)
데이터를 저장하는 공간 + 다음 주소를 가리키는 공간으로 나누어져 있다.
메모리공간낭비가적지만링크메모리가필요하고,링크하나에4byte메모리를차지한다프로그램이수행되는동안크기가동적으로커지거나작아진다마지막항목은Null을가리키고있다.
Linke List의 종류
단일 연결 리스트 ( Singly Linked List )
단일 연결 리스트는 각 노드에 자료 공간과 한 개의 포인터 공간이 있고, 각 노드의 포인터는 다음 노드를 가리킨다.
이중 연결 리스트 ( Doubly Linked List )
이중 연결 리스트의 구조는 단일 연결 리스트와 비슷하지만, 포인터 공간이 두 개가 있고 각각의 포인터는 앞의 노드와 뒤의 노드를 가리킨다.
원형(환형) 연결 리스트 ( Circular Linked List )
원형 연결 리스트는 일반적인 연결 리스트에 마지막 노드와 처음 노드를 연결시켜 원형으로 만든 구조이다.
이중 원형(환형) 연결 리스트 ( Doubly Circular Linked List )
이중 원형 연결 리스트는 이중 연결 리스트의 마지막 노드와 처음 노드를 연결시켜 원형으로 만든 구조이다.
출처: https://takeuu.tistory.com/172
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
class LinkedList {
constructor() {
this.head = null;
this.tail = null;
this._size = 0;
}
//주어진 값을 연결 리스트의 끝에 추가합니다.
addToTail(value) {
//해당 함수가 실행 될 때마다 value값을 가지는 Node의 인스턴스를 생성.
let node = new Node(value);
//최초 데이터를 생성 할 경우
if(!this.head){
this.head = node;
this.tail = node;
this._size ++;
//데이터가 1개 이상 존재할 경우
}else{
this.tail.next = node;
this.tail = node;
this._size ++;
}
}
//주어진 값을 찾아서 연결을 해제(삭제)합니다
//찾은 후 링크를 다시 걸어준다.
remove(value) {
//값이 없을경우
if(!this.head){
return undefined;
}
//삭제할 value가 head일 경우
if(this.head.value === value){
this.head = this.head.next;
this._size--;
}
let previousNode = this.head;
let currentNode = this.head.next;
while(currentNode ){
if(currentNode.value === value){
previousNode.next = currentNode.next;
this._size--;
break;
}else{
previousNode = currentNode;
currentNode = currentNode.next;
}
}
}
//주어진 인덱스의 노드를 찾아서 반환합니다.
//값이 아니라 노드를 반환해야 하는 것에 주의하세요.
//해당 인덱스에 노드가 없다면 undefined를 반환합니다.
getNodeAt(index) {
let currentNode = this.head;
if(this._size < index){
return undefined;
}else{
for(let i = 0 ; i < this._size; i++){
if(i === index){
return currentNode;
}
currentNode = currentNode.next;
}
}
}
//연결리스트에 주어진 값을 가지는 노드의 존재 여부를 반환합니다.
contains(value) {
let currentNode = this.head;
while(currentNode ){
if(currentNode.value === value){
return true;
}
currentNode = currentNode.next;
}
return false;
}
//주어진 값의 인덱스를 반환합니다. 없을 경우 -1을 반환합니다.
indexOf(value) {
let count = 0;
//현재 인스턴스의 head
let currentNode = this.head;
//현재 인스턴스 부터 next 에 저장되어 있는 node를
//모두 순회하면서 각 node의 value값이 파라미터와
//같은지 확인한다.
while(currentNode){
if(currentNode.value === value){
return count;
}
count ++;
currentNode = currentNode.next;
}
return -1;
}
size() {
return this._size;
}
}
let linkedList = new LinkedList();
linkedList.addToTail('a');
linkedList.addToTail('b');
linkedList.addToTail('c');
/*
Node {value: 'a', next: Node}
next:Node {value: 'b', next: Node}
next:Node {value: 'c', next: null}
next:null
*/
console.log(linkedList.size());//3
console.log(linkedList.indexOf('b')); //1
console.log(linkedList.contains('b'));//true
linkedList.remove('b');
console.log(linkedList.size());//2
console.log(linkedList.indexOf('b')); //-1
console.log(linkedList.contains('b'));//false
/*
Node {value: 'a', next: Node}
next:Node {value: 'c', next: null}
next:null
*/