[자료구조] - LinkedList

연결리스트 (LinkedList)

각 노드가 데이터마다 포인터를 가지며, 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 구조이고, 데이터 수에 맞춰 효율적으로 메모리를 활용할 수 있는 자료구조이다.

노드 : 데이터와 다음 노드를 가르키는 포인터로 이루어져있다. 데이터에는 값이 들어가고, 포인터에는 또다른 Node를 가르키는 주소가 들어간다.

자료출처 - 위키백과https://ko.wikipedia.org/wiki/%EC%97%B0%EA%B2%B0_%EB%A6%AC%EC%8A%A4%ED%8A%B8

연결 리스트

• 위 그림과 같이 노드들이 일렬로 연결된 자료구조 형태.
• 첫번째 노드를 HEAD라고 한다.
• 데이터의 추가,삭제등이 저장공간의 낭비없이 효율적으로 처리 가능.

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() : 연결리스트 내 노드 개수 확인
LinkedList.prototype.size = function(){
	return this.length;
};

//isEmpty() : 객체 내 노드 존재 여부 파악 
LinkedList.prototype.isEmpty = function(){
	return this.length === 0;    //0이면 true 노드가 있다면 false 반환
};

//printNode() : 노드 출력
LinkedList.prototype.printNode = function(){
  	// node라는 변수에 제일 첫 head를 넣어주고 다음 노드로 업데이트를 해준다. 마지막 null을 만날때까지
	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,
    index = 0,
    prev;
  	
  	if(position === 0){
    	node.next = current;
     	this.head = node;
    }else{
    	while(index++ < position){
        	prev = current;
          	current = current.next;
        }
      	node.next = current;
      	prev.next = node;
    }
  
  	this.length++;
  
  
  
};