연결 리스트는 노드(Node)라는 객체로 이루어져 있고 각 노드가 데이터(data field)와 포인터(linked field)를 가지며, 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조이다.
자료가 연결되어 있어 새로운 자료를 앞쪽에 추가,삭제 시 유용하게 사용할 수 있다. 하지만 특정 자료를 불러올 때는 무조건 앞쪽부터 순회하며 찾는 과정을 거치기 때문에 이때는 배열을 사용하는 편이 효율적이다.
연결 리스트에는 데이터를 저장하는 역할을 하는 프로퍼티(여기서는 data)와 다음 노드의 위치를 가리키는 포인터 역할을 하는 프로퍼티(next)가 각각 존재한다.
data - 데이터를 저장하는 공간
pointer - 다음 주소를 가리키는 공간(next address)[data | next] Node
head - 가장 최초의 주소를 가리키는 노드
tail - 마지막 노드 - 포인터는 'null'을 가리킨다.head -> [ 0 | ]->[ 0 | ]->[ 0 | ]-> null Node Node Node
// Node(): data와 point를 가지고 있는 객체
function Node(data) {
this.data = data;
this.next = null;
}
// LinkedList(): head와 length를 가지고 있는 객체
function LinkedList() {
this.head = null;
this.length = 0;
}
노드 개수 / 비어있는지 확인 / 노드 출력 : size()
isEmpty()
printNode()
노드 추가 : append()
insert()
노드 삭제 : remove()
removeAt()
데이터 위치 확인 : indexOf()
size는 length와 같고 비어있는지 확인을 위해 isEmpty라는 메서드를 정의한다.
LinkedList.prototype.size = function(){
return this.length;
}
LinkedList.prototype.isEmpty = function(){
return this.length === 0;
}
노드를 출력하기 위한 메서드이다. LinkedList를 탐색을 하면서 데이터를 찍어주고, 마지막엔 null을 출력한다. 개행없이 옆으로 출력하고, 화살표를 그려서 데이터의 연결이 가시적으로 보이도록 되어있다.
LinkedList.prototype.printNode = function(){
for(let node = this.head; node != null; node = node.next){
process.stdout.write(`${node.data} -> `);
}
console.log('null');
}
LinkedList.prototype.append = function(value){
let node = new Node(value),
current = this.head;
if(this.head === null){
this.head = node;
} else {
while(current.next != null){
current = current.next;
}
current.next = node;
}
this.length++;
}
let ll = new LinkedList();
ll.append(1);
ll.append(10);
ll.append(100);
ll.printNode();
1 -> 10 -> 100 -> null
[ prev | ]<-[ new node | ]<-[ current | ]
LinkedList.prototype.insert = function(value, position = 0){
// 범위체크 (position이 음수이거나, 길이를 벗어나면 리스트에 추가하지 않는다)
if(position < 0 || position > this.length){
return false;
}
let node = new Node(value),
current = this.head,
index = 0,
prev; //이전 노드 값
// 포지션이 없을 때
if(position === 0){
node.next = current;
this.head = node;
// 포지션이 있을 때
} else {
while(index++ < position){
// position=1일때:코드 1회수행(index가 0부터 시작이므로), position=3일때:코드 3회수행
prev = current;
current = current.next;
}
node.next = current;
prev.next = node;
}
this.length++;
return true;
}
ll.insert(1);
ll.insert(10);
ll.insert(100);
ll.printNode();
ll.insert(2,1);
ll.insert(3,3);
ll.printNode();
100 -> 10 -> 1 -> null
100 -> 2 -> 10 -> 3 -> 1 -> null
LinkedList.prototype.remove = function(value){
// 초기화
let current = this.head, // 최초 노드
prev = current;
while(current.data != value && current.next != null){
prev = current;
current = current.next;
}
// value가 없으면 끝낸다
if(current.data != value){
return null;
}
// value가 있을 때
if(current === this.head){ // current가 가장 최초 노드일때 수행됨.
this.head = current.next;
} else {
prev.next = current.next;
}
this.length--;
return current.data;
}
console.log(ll.remove(1000));
ll.printNode();
console.log(ll.remove(1));
ll.printNode();
console.log(ll.remove(2));
ll.printNode();
console.log(ll.remove(100));
ll.printNode();
null
100 -> 2 -> 10 -> 3 -> 1 -> null
1
100 -> 2 -> 10 -> 3 -> null
2
100 -> 10 -> 3 -> null
100
10 -> 3 -> null
LinkedList.prototype.removeAt = function(position = 0){
if(position < 0 || position >= this.length){
return null;
}
let current = this.head,
index = 0,
prev;
if(position === 0){
this.head = current.next;
} else {
while(index++ < position){
prev = current;
current = current.next;
}
prev.next = current.next;
}
this.length--;
return current.data;
}
console.log(ll.removeAt(1000));
ll.printNode();
console.log(ll.removeAt(1));
ll.printNode();
console.log(ll.removeAt(2));
ll.printNode();
console.log(ll.removeAt());
ll.printNode();
null
100 -> 2 -> 10 -> 3 -> 1 -> null
2
100 -> 10 -> 3 -> 1 -> null
3
100 -> 10 -> 1 -> null
100
10 -> 1 -> null
LinkedList.prototype.indexOf = function(value){
let current = this.head,
index = 0;
// current가 null이 아닐때까지 반복
while(current != null){
if(current.data === value){
return index;
}
index++;
current = current.next;
}
// 값이 없으면 -1을 반환
return -1;
}
indexOf와 removeAt을 같이 사용해서 remove의 역할을 하도록 만들 수 있다.
LinkedList.prototype.remove2 = function(value){
let index = this.indexOf(value);
return this.removeAt(index);
}
console.log(ll.remove(1000));
ll.printNode();
console.log(ll.remove2(1));
ll.printNode();
console.log(ll.remove2(2));
ll.printNode();
console.log(ll.remove2(100));
ll.printNode();
null
100 -> 2 -> 10 -> 3 -> 1 -> null
1
100 -> 2 -> 10 -> 3 -> null
2
100 -> 10 -> 3 -> null
100
10 -> 3 -> null
참조
https://overcome-the-limits.tistory.com/16
https://sycho-lego.tistory.com/17