이중 연결 리스트
- 이중 연결 리스트 #1 (append, pop 구현하기)
어제 워밍업(?) 느낌으로 가장 간단한 두가지 기능만 구현했었다.
나머지 구현한 메서드는 다음과 같다.
- n번째 위치에 노드 추가
- n번째 위치 노드 삭제
- 특정 값을 가진 노드 삭제
- 현재 노드를 순서대로 출력
- 현재 노드를 역순으로 출력
- 이중 연결 리스트가 비어있는지 확인
- 현재 이중 연결 리스트의 길이 출력
insert 부분을 디버깅하면서 계속 수정하느라 구현하는데 가장 오래 걸렸다...
가장 오래 걸린 만큼 코드도 지저분하지만..ㅠㅠ
insert
n번째 위치에 노드 추가하기
insert 메서드는 index와 추가할 노드의 값을 인수로 받는다.
DoublyLinkedList.prototype.insert = function (index, data) {
let currentIndex = 0;
let newNode = new Node(data);
let currentNode = this.head;
if (index < 0 || index > this.length) {
return console.log("인덱스 범위를 벗어남.");
}
// 현재 노드 0이면서 삽입할 인덱스 값이 0인 경우
if (index === 0 && this.length === 0) {
this.head = newNode;
this.tail = newNode;
} else if (index === 0) {
currentNode.prev = newNode;
newNode.next = currentNode;
this.head = newNode;
} else if (index === this.length) {
// 마지막에 추가하는 경우
newNode.prev = this.tail;
this.tail.next = newNode;
this.tail = newNode;
} else {
while (currentNode.next !== null) {
if (currentIndex === this.length - 1) break;
if (currentIndex === index) break;
currentNode = currentNode.next;
currentIndex++;
}
newNode.next = currentNode;
newNode.prev = currentNode.prev;
newNode.prev.next = newNode;
currentNode.prev = newNode;
}
this.length++;
return console.log(`${data}를 노드에 추가했습니다.`);
};인수로 받은 index가 현재 이중 연결 리스트의 범위를 넘어가는 경우 예외처리를 먼저 해주었다.
index가 0이면서 현재 이중 연결 리스트의 길이가 0인 경우엔 아무 노드가 없다는 것을 의미하므로 this.head와 this.tail을 새로운 노드로 만들어주면 된다.
하지만, 현재 이중 연결리스트의 길이가 1 이상이면서(노드가 1개 이상 존재) 0번째 인덱스 위치에 새로운 노드를 추가하고자 하는 경우엔 맨 앞의 노드를 새로운 노드로 변경시켜주어야 한다.
그리고 마지막 인덱스 위치에 새로운 노드를 추가하는 경우엔 tail 부분을 새로운 노드로 변경 시켜주고 기존 tail 노드에게는 다음 노드의 위치 값으로 새로운 노드를 연결 시켜주면 된다.
마지막 else 부분은 삽입할 새로운 노드의 앞 뒤로 노드가 존재하는 경우이다.
우선 위치할 n번째 만큼 위치를 이동 시켜야 하므로 while문을 사용했다. 만약 인덱스를 벗어나거나 넣고자 하는 위치 index에 도달한 경우 while문을 중단하도록 작성했다.
while문이 종료된 이후에 노드의 위치를 조절해주면 된다. 새로운 노드의 앞과 뒤에 각각 위치를 설정해주고, 새로운 노드의 앞에 존재하는 노드에게 next 값으로 새로운 노드를 전달해주고, currentNode의 값은 현재 새로운 노드가 들어갈 위치에 있던 노드이므로 currentNode의 prev로 새로운 노드를 설정해주면 된다.
이 과정이 끝나면 이중 연결 리스트에 새로운 노드가 삽입됐으므로 길이를 1 증가시켜주면 된다.
removeNode
특정 위치의 노드를 제거하는 메소드이다.
index 값을 인수로 받는다.
DoublyLinkedList.prototype.removeNode = function (index) {
let currentIndex = 0;
let currentHeadNode = this.head;
let currentTailNode = this.tail;
if (index < 0 || index >= this.length) {
return console.log("인덱스 범위를 벗어남");
}
if (index === 0 && this.length === 1) {
this.head = null;
this.tail = null;
} else if (index === 0) {
this.head = currentHeadNode.next;
this.head.prev = null;
} else if (index === this.length - 1) {
currentTailNode.prev.next = null;
this.tail = null;
} else {
while (currentIndex !== index) {
currentHeadNode = currentHeadNode.next;
currentIndex++;
}
currentHeadNode.prev.next = currentHeadNode.next;
currentHeadNode.next.prev = currentHeadNode.prev;
}
this.length--;
return console.log(`${index}번째 노드가 삭제되었습니다.`);
};
먼저 가장 중요한 범위를 체크해주고 insert 메소드 때 작성했던 것과 마찬가지로 노드가 아예 없는 경우와 맨 앞 노드를 삭제, 맨 뒤 노드 삭제하는 부분을 if-else if로 해결해주었다.
노드와 노드 사이에 낀 노드를 삭제하는 경우 while문을 사용하여 삭제할 index에 도달했을 때 각각의 노드의 prev와 next의 값을 조정해주었다.
insert에 비해서 구현자체는 완전 천사 같았던 removeNode!
지금와서 생각해보니 보니 함수 작명을 그냥 remove로 할걸 그랬나보다.
이름만 바꾸면 되긴 한데 지금보니 뭔가 통일성이 없어서 눈에 띈다..
removeNodeValue
앞에 removeNode가 index를 기준으로 노드를 삭제했다면 removeNodeValue는 특정 노드의 data 값을 기준으로 노드를 삭제하는 메서드이다.
DoublyLinkedList.prototype.removeNodeValue = function (value) {
let currentIndex = 0;
let currentNode = this.head;
let isFound = false;
if (this.length === 0) return console.log("삭제할 노드가 없습니다");
while (currentNode.next !== null) {
if (currentNode.data === value) {
isFound = true;
break;
}
currentNode = currentNode.next;
currentIndex++;
}
// 마지막에 위치한 노드 data가 지울 value인 경우
if (currentIndex === this.length - 1 && value === currentNode.data) {
isFound = true;
if(currentNode.prev === null){
this.head = null;
this.tail = null;
}else {
currentNode.prev.next = null;
}
}
if (!isFound) return console.log("해당 값이 존재하지 않습니다.");
if (currentIndex === 0) {
this.head = currentNode.next;
currentNode.prev = null;
} else if (currentIndex !== this.length - 1) {
currentNode.prev.next = currentNode.next;
currentNode.next.prev = currentNode.prev;
}
this.length--;
return console.log(`${value} 값을 가진 노드가 삭제되었습니다.`);
};현재 이중 연결 리스트의 길이가 없는데 해당 메서드를 호출할 경우 삭제할 노드가 없다는 로그를 찍고 리턴시켰다.
그리고 while문의 조건에는 다음 노드의 next가 null인 경우 종료되므로 마지막의 노드 data 값을 따로 확인하는 if문이 필요하다고 생각해서 if문으로 현재 인덱스가 이중 연결 리스트의 끝인지 확인하고 삭제할 value와 현재 노드의 data값이 일치하는지 확인해서 true인 경우에 isFound의 값을 true로 만들어주었다.
만약 이 과정을 다 거쳤음에도 isFound가 false라면 애초에 이중 연결 리스트에 삭제할 값이 존재하지 않았음을 의미하므로 "해당 값이 존재하지 않습니다."라고 콘솔 로그를 출력하고 리턴하도록 만들었다.
0번째 인덱스의 위치한 값이거나 맨 마지막 인덱스에 위치한 값을 지우는 경우에도 if문을 통해 노드의 next, prev를 조정하도록 만들었다.
이 과정을 통해 중간에 return을 만나지 않았다면 노드가 삭제됐음을 의미하므로 현재 이중 연결 리스트의 길이를 1 빼주면 된다.
다 된줄 알고 마지막 테스트 중이었는데 코드가 하나 잘못됐음을 느끼고 중간에 if문을 하나 더 추가했다.. 현재 노드의 prev가 null인 경우 if문을 추가했음
printNode
현재 노드를 순서대로 출력하는 메서드이다.
이중 연결 리스트의 경우 next와 prev가 있기 때문에 head부터 next가 null이기 전까지의 모든 값을 순서대로 출력할 수 있도록 만들었다.
코드의 확장성을 생각해서 배열로 반환하도록 했다.
DoublyLinkedList.prototype.printNode = function () {
let currentNode = this.head;
let nodes = [];
if (this.length === 0) return console.log("출력할 노드 없음");
if (this.length >= 1) {
while (currentNode.next !== null) {
nodes.push(currentNode.data);
currentNode = currentNode.next;
}
}
nodes.push(currentNode.data);
return nodes;
};출력하는 것은 특별히 어려움이 없었어서.. 특별히 코멘트 할 게 없지만 ㅋㅋ (n번째 추가가 너무 악랄했기 때문에ㅠㅠ)
이중 연결 리스트의 현재 길이가 0인 경우 아무 노드가 없다는 것을 의미하므로 출력할 노드가 없다는 로그를 찍도록 했다.
1개 이상의 노드가 존재하는 경우 노드의 next가 null이 아닐 때까지 반복문을 통해 nodes 배열에 data를 하나씩 추가시킨다.
이경우 마지막에 위치한 data는 제외되기 때문에 리턴 전에 currentNode.data를 한번 더 push해주어야 한다.
printReverseNode
앞선 printNode가 정방향으로 노드의 data값을 출력했다면 이번엔 tail의 data부터 head의 data를 출력하는 역방향 print 메서드이다.
DoublyLinkedList.prototype.printReverseNode = function () {
let currentIndex = this.length - 1;
let currentNode = this.tail;
let nodes = [];
if (this.length === 0) return nodes;
while (currentIndex >= 0) {
nodes.push(currentNode.data);
currentNode = currentNode.prev;
currentIndex--;
}
return nodes;
};정방향때와 마찬가지로 확장성을 고려해서 배열을 사용했다.
이번엔 거꾸로 시작하기만 하면 되므로 정방향과 로직은 동일하다.
isEmpty
현재 이중 연결 리스트가 비어있는지 확인하는 메서드이다.
DoublyLinkedList.prototype.isEmpty = function () {
return this.length === 0;
};현재 길이를 기준으로 t/f로 반환하기만 하면 되므로 매우 간단한 코드이다.
printLength
현재 이중 연결 리스트의 길이를 반환해주는 메서드이다.
마찬가지로 그냥 현재 길이를 리턴하면 되므로 심플!
DoublyLinkedList.prototype.printLength = function () {
return this.length;
};테스트 해보기
let dll = new DoublyLinkedList();
dll.append(1);
dll.append(2);
dll.append(3);
console.log(dll.printNode()); // [1, 2, 3]
console.log(dll.printReverseNode()); // [3, 2, 1]dll.append(1);
dll.insert(0, "0번째에 추가 할게요");
dll.insert(2, "2번째에 추가 할래요");
console.log(dll.printNode()); // ["0번째에 추가 할게요", 1, "2번째에 추가 할래요"]
console.log(dll.printReverseNode()); // ["2번째에 추가 할래요", 1, "0번째에 추가 할게요"]
dll.removeNode(0);
console.log(dll.printNode()); // [1, "2번째에 추가 할래요"]
console.log(dll.printReverseNode()); // ["2번째에 추가 할래요", 1]
이번에 직접 이중 연결 리스트를 구현하면서 알게된 점
insert 로직이 생각이상으로 복잡했다. 처음에 와! 다 구현했네! 하고 디버깅하면서 테스트 해봤는데 중간에 로직이 잘못됐음을 깨닫고 처음부터 다시 작성하는 일이 발생했다.. 또륵.
제일 어려웠던 insert!! 어렵다기보단 사실 복잡해서 헷갈렸다가 더 올바른 표현인 것 같지만 어쨌든 단일 연결 리스트를 만들 때와는 또 다른 재미가 있었던 것 같다.
일단 혼자서 테스트 해봤을 때는 특별히 버그는 없는 것 같은데 또 있을 지도 모르겠다.....
있다면 고쳐야지.. 수정했다 싶으면 자꾸 나오는 버그쨩ㅠ
