공부합시다.

실행환경 : 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

실행환경 : nodejs

javascript를 이용한 stack 구현

배열의 구조,api를 활용
javascript의 약한 언어의 특징 때문에 쉬운 구현이 가능

때문에 크기에 제한을 두지 않는다.(메모리 크기까지 가능)
javascript의 array 메소드에 push, pop을 활용하여 간단한 구현을 하였습니다.

stack의 특징

last in first out, first in last out 특징
인터럽트, tree의 전위 순회 등에 쓰인다.

(제 tree의 구현에 사용했습니다.)

stack용어

push(,= put)

삽입, stack의 맨 위에 해당 엘리먼트를 삽입한다.

pop(,= get)

삭제, stack의 맨 위에 해당하는 엘리먼트를 리턴, 삭제한다.

맨 위의 값, push한 값, pop이 될 값이 된다.

buttom

맨 아래, top == buttom이라면 stack이 비었음을 의미한다.

var stack = function(){
 this.datas = [];
}


stack.prototype.isEmpty = function(){
  return this.datas.length==0?true:false;
}
stack.prototype.length = function(){
 return this.datas.length;
}
stack.prototype.push = function(element){

 this.datas.push(element);
 // console.log("-------------------------------------------------------------");
 // console.log("push ",element);
 // console.log("-------------------------------------------------------------");
 // this.print();

}
stack.prototype.pop = function(){
 element = this.peek();
 this.datas.pop();
 // console.log("-------------------------------------------------------------");
 // console.log("pop!");
 // console.log("return",element);
 // console.log("-------------------------------------------------------------");
 // this.print();
 return element;
}
stack.prototype.peek = function(){
 element = this.datas[this.datas.length-1]==undefined?null:this.datas[this.datas.length-1];
 return element;
}
stack.prototype.toArray = function(){
 return this.datas;
}
stack.prototype.print = function(){
 var tmp = this.datas;
 for(i=tmp.length-1;0<=i;i--){
  console.log("│ "+this.datas[i]+" │");
 }
 console.log("└---┘");
}

stack.prototype.delAll = function(){
 this.datas = [];
}

// S = new stack();

// S.push(3);
// S.push(5);
// S.push(1);
// S.push(6);

// S.pop();

// S.pop();

// S.push(9);
// S.push(8);

module.exports = stack;

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

공부합시다.

2015년 4월 19일 일요일

[data structure javascript] Linked List

[data structure javascript] Stack