❓ 연결 리스트(Linked List)
- 각 노드가 데이터와 포인터를 가지며, 한 줄로 연결되어있는 방식으로 데이터를 저장하는 자료구조이다.
function Node(data) {
this.data = data;
this.next = null;
}
function LinkedList() {
this.head = null;
this.length = 0;
}
✏️ 구현 메서드
📗 size() : 노드 개수확인
LinkedList.prototype.size = function () {
return this.length;
}
📗 isEmpty() : 객체 내 노드 존재 여부 파악
LinkedList.prototype.isEmpty = function () {
return this.length === 0;
}
📗 printNode() : 노드 출력
LinkedList.prototype.printNode = function () {
for(let node = this.head; node != null; node = node.next){
process.stdout.write(`${node.data} ->`);
}
console.log("null")
}
📗 append() : 연결 리스트 가장 끝에 노드 추가
LinkedList.prototype.append = function (value) {
let node = new Node(value);
let current = this.head;
if(this.head === null){
this.head = node;
}else{
while(current.next != null){
current = current.next;
}
current.next = node;
}
this.length++;
};
📗 insert() : position 위치에 노드 추가
LinkedList.prototype.insert = function (value, position = 0){
if(position < 0 || position > this.length){
return false;
}
let node = new Node(value);
let current = this.head;
let index = 0;
let prev;
if(position === 0){
node.next = current;
this.head = node;
} else {
while(index < position){
prev = current;
current = current.next;
index++;
}
node.next = current;
prev.next = node;
}
this.length++;
return true;
}
📗 remove() : value 데이터를 찾아 노드 삭제
LinkedList.prototype.remove = function (value) {
let current = this.head;
let prev = current;
while(current.data != value && current.next != null){
prev = current;
current = current.next;
}
if(current.data != value) {
return null;
}
if(current === this.head){
this.head = current.next;
} else {
prev.next = current.next;
}
this.length--;
}
📗 removeAt() : position 위치 노드 삭제
LinkedList.prototype.removeAt = function (position = 0) {
if(position < 0 || position >= this.length) {
return null;
}
let current = this.head;
let index = 0;
let 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;
};
📗 indexOf() : value 값을 갖는 노드 위치 반환
LinkedList.prototype.indexOf = function (value) {
let current = this.head;
let index = 0;
while(current != null){
if(current.data === value){
return index;
}
index++;
current = current.next;
}
return -1;
}
📗 remove2() : indexOf + removeAt
LinkedList.prototype.remove2 = function(value) {
let index = this.indexOf(value);
return this.removeAt(index);
}