생각을 개발하자, 박진형

[자료구조, 알고리즘] 리스트#4 - DoublyLinkedList 본문

Data structure & Algorithm/data structure_algorithm

[자료구조, 알고리즘] 리스트#4 - DoublyLinkedList

imjinbro imjinbro 2017.09.15 02:58
[연결리스트]
- 노드 간의 연결된 형태 : 실제로는 각각 따로 떨어져있음, 이어서 붙여놓음


[양방향 연결리스트 객체의 타입 설계]
- 추가해! : 연결리스트에 데이터 노드를 추가(연결), 길이에 따라 다르게(0인 경우 1이상인 경우), 데이터를 받아서 데이터 노드에 넣기
- 첫번째로 가 : 현재 노드를 가장 첫번쨰 노드(헤드노드)로
- 다음번째로 가 : 현재 노드를 기준으로 다음노드로 이동
- 이전번째로 가 : 현재 노드를 기준으로 전 노드로 이동
- 삭제해 : 현재 선택된 노드를 삭제하는데, 선택된게 헤드인지, 중간인지, 마지막인지, 다음은 있는지 없는지 잘 따져서 노드 연결 끊이지않게 하기
- 선택된 노드를 줘 : 현재 선택되어진 노드를 리턴
- 개수 : 현재 양방향 연결리스트에 저장된 데이터가 몇개 있어?

- 양방향 연결리스트 : 단순 연결리스트 + 노드 선택을 앞 뒤로 할 수 있음
- 구현
var DoublyLinkedList = (function () {
var Node = function(data){
this.data = data;

/* 데이터 탐색에 필요한 필드 */
this.before = null;
this.next = null;
}

var DoublyLinkedList = function(){
/* 데이터 노드 탐색, 조회, 삭제 필요한 필드 */
this.head = null;
this.current = null;
/* 데이터 노드 저장 개수 필드 */
this.length = 0;
}

DoublyLinkedList.prototype = {
/* 공용 인터페이스 목록 + 메서드 */
insert: function(data){
if(!data){
console.log("저장할 데이터를 입력해주세요");
return false;
}

var insertNode = new Node(data);
if(this.count() < 1){
this.head = insertNode;
} else {
/* 헤드 노드를 뒤로 밀어내고 새롭게 추가하는 노드가 헤드 노드가 됨 */
var preNode = this.head;
preNode.before = insertNode;
insertNode.next = preNode;

this.head = insertNode;
}

this.length += 1;
return true;
},
first: function(){
if(this.count() < 1){
return false;
}
this.current = this.head;
return true;
},

next: function(){
if(!this.current || !this.current.next){
return false;
}
this.current= this.current.next;
return true;
},

before: function(){
if(!this.current || !this.current.before){
return false;
}
this.current = this.current.before;
return true;
},

get: function(){
if(!this.current){
return false;
}
return this.current;
},
remove: function(){
if(!this.current){
return false;
}

var targetNode = this.current;
var deleteData = targetNode.data;
//null 처리 해줘야함 - 모두 삭제되었을 때 before, next

if(targetNode === this.head){
/* 타겟노드가 헤드일 때 분기처리 : 헤드 다음이 있는지에 따라 */
if(targetNode.next){
var nextNode = targetNode.next;
nextNode.before = null;
targetNode.next = null;

this.head = nextNode;
this.current = null;

this.first();
} else{
this.head = null;
this.current = null;
}

} else {
/* 헤드가 아닐 때 분기처리 : 위치에 따라(중간과 끝) */
if(targetNode.before && targetNode.next){
targetNode.before.next = targetNode.next;
targetNode.next.before = targetNode.before;
} else {
targetNode.before.next = null;
}

this.current = targetNode.before;
}

//할당변수 메모리 해제, 참조 변수 X - 객체 메모리 할당 해제
targetNode = null;
this.length -= 1;
return "삭제된 데이터 : " + deleteData;
},

count: function(){
return this.length;
}
}

return DoublyLinkedList;

})();