연결 리스트는 그 크기가 동적인 자료구조로, 자료구조를 구성하는 요소, -우리는 이것을 노드(Node) 라고 부릅니다노드의 연결로 이루어진 자료 구조입니다. 연결 리스트의 어떠한 임의의 지점에 데이터의 추가와 삭제를 할 경우, O(1) (상수 시간)의 시간 복잡도를 갖습니다. 추가와 삭제에 대해 O(n) (선형 시간)의 복잡도를 갖는 배열과는 다르죠.
다만 이 추가와 삭제 속도에 대한 대가로, 연결 리스트의 각 노드는 인덱스를 갖지 않습니다. 그래서 어떤 특정 데이터를 연결 리스트에서 검색하고자 할 경우, 처음부터 전체 연결 리스트를 훓어야 하며, 이는 O(n) (선형 시간)의 복잡도를 필요로 합니다.
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
class LinkedList {
constructor() {
this.head = null;
this.tail = null;
this._size = 0;
}
addToTail(value) {
let node = new Node(value); //new node 생성
if(!this.head) { //head가 비어있다면 첫번째 연결이기떄문에 head와 tail에 node 연결
this.head = node;
this.tail = node;
this._size++;
} else { //head가 비어 있지 않다면 tail.next에 node 연결, tail에 node 연결, size++
this.tail.next = node;
this.tail = node;
this._size++;
}
return node;
}
remove(value) {
//주어진 값을 찾아서 연결을 해제(삭제)합니다
if(!this.head) { //만약에 헤드가 없다면 undefined 리턴.
return undefined;
}
if(this.head.value === value) { //만약에 헤드 value와 입력받은 value가 같다면
this.head = this.head.next; // head는 head.next로 설정. (헤드 없애기)
this._size--;
return this; //현재 오브젝트 리턴.
}
let prevNode = this.head; //head를 prevNode로 설정. (0번째)
let currentNode = this.head.next; //head.next를 currentNode 설정. (1번째)
while(currentNode) { //currentNode 있을 때까지.
if(currentNode.value === value) { //만약 currentNode.value가 value와 값이 같다?
break;
}else { // 만약 값이 같지 않다?
prevNode = currentNode;
currentNode = currentNode.next; //한 칸씩 당겨 준다
this._size--;
}
}
prevNode.next = currentNode.next; //(currentNode.value 값이 같을 때)
return this;
}
getNodeAt(index) {
//주어진 인덱스의 노드를 찾아서 반환합니다. 값이 아니라 노드를 반환해야 하는 것에 주의하세요. 해당 인덱스에 노드가 없다면 undefined를 반환합니다.
let currentNode = this.head;
if(index > this._size) { //입력받은 index가 size보다 크면 undefined에 저장
return undefined;
} else { //index가 size보다 작으면 for문을 돌리는데, i<index로 설정하고 1번의 변수를 1번의 변수.next로 설정해서 index까지 도달.
for(let i = 0; i < index; i++) {
currentNode = currentNode.next;
}
}
return currentNode; //해당 인덱스 리턴
}
contains(value) {
//연결리스트에 주어진 값을 가지는 노드의 존재 여부를 반환합니다.
let currentNode = this.head;
while (currentNode) { //this.head가 있을때까지
if( currentNode.value === value) { //입력받은 value와 currentNode.value가 같다면 리턴 true.
return true;
} else { // 같지 않다면 currentNode = currentNode.next
currentNode = currentNode.next;
}
}
return false; //다 돌았음에도 불구하고 없다면 false 리턴
}
indexOf(value) {
//주어진 값의 인덱스를 반환합니다. 없을 경우 -1을 반환합니다.
let currentNode = this.head; //head변수
let count = 0; //index로 사용할 count변수
while (currentNode) { //currentNode가 있을때까지
if(currentNode.value === value) { //해당 인덱스와 currentNode.value가 같다면 인덱스 변수 리턴.
return count;
} else {
count++; //아니라면 index 변수++, currentNode = currentNode.next
currentNode = currentNode.next;
}
}
return -1; //다 돌았음에도 불구하고 없다면 -1 리턴.
}
size() {
return this._size;
}
}
module.exports = LinkedList;