공부합시다.: [data structure javascript] Linked List

실행환경 : nodejs
javascript를 이용한 linked list구현

node를 구현, 단순 linked list 이기 때문에 다음 느드를 가르키는 next와, 엘리먼트를 저장할 data로 구성
node를 출력하면 다음 노드, 다음 노드의 다음노드, 다음 노드의 다음 노드의 다음 노드..... 쭈욱 출력이 되지만, 실제로는 객체 값이 저장되는 것이 아니라 주소를 가르키고 있다.

javascript에서는 object(객체)에 대해서는 call by reference로 작동된다.

linked_list의 특징

노드로 구성
노드에는 값과 다음 값에 대한 주소를 가지고 있다.

장정

크기에 제한을 가지고 있지 않다.
중간 삽입, 삭제가 array에 비하여 쉽다.
삽입, 삭제에 대한 비용이 적다. O(1)
때문에 c,c++ 등에서 자료구조를 구현할때 linked list를 주로 활용한다.

단점

탐색에 있어서 단방향이다.
탐색에 대하여 비용이 크다. O(n)
때문에 삽입,삭제 에 있어서 이전 노드의 주소(객체)의 정보를 가지고 있어야 한다.
이중 연결 리스트가 방안이 될 수 있다.

linked list용어

node

하나의 객체로, 값과 다음 값으로 이루어 져 있다.

자매품

환영 연결 리스트
이중 연결 리스트

삽입 방법

삽입 할 노드의 앞의 노드를 찾는다. (이전노드)
이전 노드의 next의 주소를 삽입할 노드의 next로 넣는다.
이전 노드의 next의 주소를 삽입할 노드의 주소를 넣는다.

삭제 방법

삽입 반대로.

var linkedList = function(){
 this.length = 0;
 this.headNode = new node(null);
}


var node = function(element){
 this.data = element;
 this.next = null;
}

linkedList.prototype.add = function(element,position){
 
 //position이 null일 경우 마지막위치로
 var position = position==undefined?this.length+1:position;
 
 //입력값으로 node 생성

 var newNode = new node(element);

 var preNode = this.headNode;
 for(i = 1;i<position;i++){
  preNode = preNode.next;
 }
 newNode.next = preNode==null?null:preNode.next;
 preNode.next = newNode;

 this.length++;

 // console.log("-------------------------------------------");
 // console.log("add",element);
 // console.log("position",position);
 // console.log("-------------------------------------------");
 // this.print();
}

linkedList.prototype.remove = function(position){

 var ret = null;
 var position = position==undefined?0:position;
 if(this.isEmpty()){
  console.log("list is Empty");
 }
 else if(position<this.length){
  var preNode = this.headNode;

  for(i = 0;i<position;i++){
   preNode = preNode.next;
  }
  ret = preNode.next.data;
  preNode.next = preNode.next.next;
  
  this.length--;
 }
 else{
  console.log("index error");
 }

 // console.log("-------------------------------------------");
 // console.log("position",position);
 // console.log("remove",ret);
 // console.log("-------------------------------------------");
 // this.print();
 return ret;
}


linkedList.prototype.peek = function(position){

 var ret = null;
 var position = position==undefined?0:position;
 if(this.isEmpty()){
  console.log("list is Empty");
 }
 else if(position<this.length){
  var preNode = this.headNode;

  for(i = 0;i<position;i++){
   preNode = preNode.next;
  }
  ret = preNode.next.data;

 }
 else{
  console.log("index error");
 }

 return ret;
}

linkedList.prototype.print = function(position){
 var str = "linkedList : ";
 var node = this.headNode.next;
 while(node != null){
  str += node.data;
  str += " -> ";
  node = node.next;
 };
 console.log(str);
}


linkedList.prototype.isEmpty = function(){
 var ret = false;
 if(!this.length){
  ret = true;
 }

 return ret;
}

// list = new linkedList();

// list.add(1);

// list.add(2);

// list.add(3);

// list.add(3,1);

// list.add(1);

// list.remove();
// list.remove(3);

아래 github또는 블로그 내에 다른 tree, stack, tree에 대한 구현 글이 있습니다..
github에는 실행 데모도 있습니다.
https://github.com/ignocide/data-structure

공부합시다.

2015년 4월 19일 일요일

[data structure javascript] Linked List

댓글 없음:

댓글 쓰기