❓ 연결 리스트(Linked List)

• 각 노드가 데이터와 포인터를 가지며, 한 줄로 연결되어있는 방식으로 데이터를 저장하는 자료구조이다.

// Node() : data와 point를 가지고 있는 객체
function Node(data) {
	this.data = data;
  	this.next = null;
}

// LinkedList() : head와 length를 가지고 있는 객체
function LinkedList() {
	this.head = null;
  	this.length = 0;
}

---

✏️ 구현 메서드

📗 size() : 노드 개수확인

// size()
LinkedList.prototype.size = function () {
	return this.length;
}

📗 isEmpty() : 객체 내 노드 존재 여부 파악

// isEmpty()
LinkedList.prototype.isEmpty = function () {
	return this.length === 0;
}

📗 printNode() : 노드 출력

// printNode()
LinkedList.prototype.printNode = function () {
	for(let node = this.head; node != null; node = node.next){
    	process.stdout.write(`${node.data} ->`);
    }
  	console.log("null")
}

📗 append() : 연결 리스트 가장 끝에 노드 추가

// 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);
}