✍️ 함수의 호출과 스택에 관한 글을 보다가 linked list에 알게 되었다. javascript로 구현이 가능한 자료 구조 이며, 배열 과는 다른 이점이 언젠가 유용하게 쓰일 수 있을 것 같아 정리 해 보았다.
Linked List 란?
- 모든 요소(node)가 다음 요소에 pointer에 의해 연결 되어 있는 자료구조
장점
- 새로운 요소 삽입, 삭제 가 쉬움. (특히 앞 쪽)
- index에 의한 물리적 배치로 이루어지 지지 않았기에, 요소 삽입 / 삭제 시 구조를 재정렬 하지 않음.
단점
- 특정 요소 검색 시, 다 순회해서 찾아야 하므로 비효율적임.
구현 코드
// 요소 기본형
// next로 다음요소를 pointing 함.
class Node {
constructor(value, next = null) {
this.value = value;
this.next = next;
}
}
class LinkedList {
constructor(){
this.head = null;
this.size = 0;
}
// 첫번째 요소 추가하기
addFirst(value){
//1. 지금 head 부분에 새 node 가 들어감.
this.head = new Node(value, this.head);
//2. node 추가로 size 증가
this.size++;
}
// 마지막 요소 추가하기
addLast(value){
//0. node 생성
// 마지막 값은 next 가 null, Node의 next를 기본값을 null로 지정 했기에, value만 인자로 넣어줌
let node = new Node(value);
if(!this.head){
//1. 빈 list 인 경우,
this.head = node;
}else{
//2. node가 존재 할 경우,
//가장 끝 node를 찾기 위해 while문으로 순회(currentNode.next가 null일때(=마지막), while문 빠져나옴.)
let currentNode = this.head;
while(currentNode && currentNode.next){
currentNode = currentNode.next;
}
// 3. 기존의 마지막 node 다음으로 node 추가
currentNode.next = node;
}
}
// value의 index 반환
getIndex(value){
let currentNode = this.head;
let i =0;
while(currentNode){
// 해당 value 값을 가진 node 발견시, i 반환
if(currentNode.value===value){
return i;
}
// 해당 value 값 아닌 경우, 다음 값으로 순회, index 값 증가
currentNode = currentNode.next;
i++;
}
}
// 중간에 요소 추가하기
addAt(value, index){
// index가 list의 size 보다 큰 경우 나가기
if (index > 0 && index > this.size) {
return;
}
// 처음 에 추가할 경우 addFirst 실행
if(index === 0){
this.addFirst(value);
return;
}
const node = new Node(value);
let currentNode, prevNode;
currentNode = this.head;
let count = 0;
//1. 첫번째 요소 부터 index 값 까지 순회
// count가 index 값과 같아질 경우 while 문 나감.
while (count < index) {
prevNode = currentNode;
count++;
currentNode = currentNode.next;
}
//2. node 삽입
node.next = currentNode;
prevNode.next = node;
//3. node 추가로 size 증가
this.size++;
}
// n 번째 요소 제거하기
removeAt(index) {
// index가 list의 size 보다 큰 경우 나가기
if (index > 0 && index > this.size) {
return;
}
let currentNode = this.head;
let prevNode;
let count = 0;
if (index === 0) {
// 첫번째 요소 제거하기
this.head = currentNode.next;
} else {
//1. 첫번째 요소 부터 index 값 까지 순회
// count가 index 값과 같아질 경우 while 문 나감.
while (count < index) {
count++;
prevNode = currentNode;
currentNode = currentNode.next;
}
//2. 이전 요소의 다음을 기존의 현재요소의 다음으로 연결 하면서 현재 요소 스킵
prevNode.next = currentNode.next;
}
//3. node 삭제로 size 감소
this.size--;
}
}
const linkedList = new LinkedList();
linkedList.addFirst(100);
linkedList.addFirst(200);
linkedList.addFirst(300);
linkedList.addLast(400);
linkedList.addAt(500, 0)
linkedList.removeAt(2)
console.log(linkedList)참고 문헌
한 걸음 한 걸음 계속 걷는 자가 일류다