단일 연결리스트 복습하기
지난번 JS로 연결 리스트 만들었을 때는 class를 사용해서 만들었었는데 복습겸 이번에는 생성자 함수를 사용해서 만들어보았다.
그때는 개념을 처음 배우면서 따라 만들어보느라 어려웠었는데 이번에는 비교적 쉽게 구현할 수 있었던 것 같다.
이전에
예외처리하지 않았던 부분도 이번 코드에서는 예외 처리하는 부분도 추가해보았다. (예를 들면 연결 리스트의 길이를 초과한다거나..)
JS 코드
function LinkedList() {
this.head = null;
this.length = 0;
}LinkedList를 만드는 함수이다.
처음 head는 null로 지정하고 length도 0으로 지정해주었다.
function Node(data) {
this.data = data;
this.next = null;
}Node를 만들어주는 생성자 함수이다.
1. 노드 개수 출력
LinkedList.prototype.size = function () {
return this.length;
};
현재 연결 리스트의 길이(노드 개수)를 출력해주는 함수이다.
2. 현재 모든 노드 출력
LinkedList.prototype.printNode = function () {
let currentNode = this.head;
let print = [];
while (currentNode !== null) {
print.push(currentNode.data);
currentNode = currentNode.next;
}
return print;
};현재 노드를 배열로 반환하도록 했다.
노드가 없는 경우 빈 배열이 반환된다.
3. 연결 리스트가 비어있는지 확인
LinkedList.prototype.isEmpty = function () {
return this.length === 0;
};연결 리스트가 비어있는 경우 true를 반환한다.
4. 맨 뒤에 노드 추가하기
LinkedList.prototype.append = function (value) {
let currentNode = this.head;
let node = new Node(value);
// 연결 리스트 비어있는지 확인 후
// 비어 있는 경우 맨 앞 head에 추가
if (this.length === 0) {
this.head = node;
} else {
while (currentNode.next !== null) {
currentNode = currentNode.next;
}
currentNode.next = node;
}
this.length++;
};현재 연결 리스트가 비어있는 경우(길이가 0일 때)
맨 앞에 노드를 추가하고 그렇지 않은 경우 현재 노드의 다음 데이터가 null이면 해당 위치에 노드를 삽입한다.
추가했으니 연결 리스트의 길이도 증가 시켜주어야 한다.
5. n번째 위치에 노드 추가하기
// n번째 위치에 노드 추가
LinkedList.prototype.insert = function (value, index = 0) {
let idx = 0;
let currentNode = this.head;
let preNode;
let node = new Node(value);
if (this.length === 0) {
this.head = node;
} else if (index < 0 || index > this.length) {
return console.log(`out of range`);
} else {
if (index === 0) {
this.head = node;
node.next = currentNode;
} else {
while (idx !== index) {
preNode = currentNode;
currentNode = currentNode.next;
idx++;
}
preNode.next = node;
node.next = currentNode;
}
}
this.length++;
};0번째에 추가 할 경우의 문제점을 초반에 캐치 못해서 다 만들고 나중에 추가 수정하면서 코드를 더 추가했더니
if-else가 잔뜩 생겨버렸다..
노드의 값과 인덱스를 파라미터로 받아서 해당 인덱스 위치에 노드를 추가한다.
현재 연결리스트 노드가 없는 경우 가장 앞쪽에 노드를 추가시킨다.
노드 사이를 비집고 들어가야 하기 때문에 새로운 노드의 앞과 뒤 노드에게 주소를 주고 받아야 한다.
앞의 노드에게는 새로운 노드의 주소를 주고,
새로운 노드는 뒤에 위치할 노드의 주소를 받아야 한다.
preNode.next = node;
node.next = currentNode;while 반복문 바깥부분의 이 코드를 의미한다.
currentNode가 현재 추가할 노드의 위치에 있었던 애라서 currentNode의 위치가 뒤로 하나 밀려나간다.
6. 특정 값을 가진 노드 삭제하기
LinkedList.prototype.remove = function (value) {
let index = 0;
let node = this.head;
let prevNode;
if (this.length === 0) return; // 노드가 없는 경우 리턴
while (node.data !== value && node.next !== null) {
prevNode = node;
node = node.next;
index++;
}
if (index === 0) {
this.head = node.next;
} else {
prevNode.next = node.next;
}
this.length--;
//삭제한 노드 반환
return node;
};연결 리스트를 다 돌아도 해당 값을 가진 노드가 없거나 노드의 데이터 값과 찾는 노드의 값이 같은 경우 반복문이 종료된다. 애초에 0번째 위치인 경우엔 반복문을 돌지 않기 때문에 this.head 값을 현재 노드의 다음 노드 주소로 연결 시켜주면 된다.
7. 노드의 특정 값으로 노드 위치 (인덱스) 찾기
LinkedList.prototype.indexOf = function (value) {
let index = 0;
let node = this.head;
let isFound = true;
if (this.length === 0) return;
while (node.data !== value) {
node = node.next;
index++;
if (node.next === null) {
isFound = false;
break;
}
}
return isFound ? index : -1;
};코드 짜면서 해당 값을 찾지 못하는 경우를 생각하지 못했었다.
블로그에 정리해서 다시 올리려고 테스트 하면서 예외처리를 안한 부분이 있었구나를 깨닫고... ㅋㅋㅋ 추가해보았다.
찾지 못한 경우 -1을 반환한다. 찾은 경우 해당 인덱스 변호가 반환된다.
8. 특정 위치의 노드 삭제하기
LinkedList.prototype.removeAt = function (removeIndex) {
let idx = 0;
let node = this.head;
let prevNode;
if (removeIndex < 0 || removeIndex >= this.length) {
return `out of range`;
}
if (removeIndex === 0) {
this.head = node.next;
} else {
while (idx !== removeIndex && node.next !== null) {
prevNode = node;
node = node.next;
idx++;
}
prevNode.next = node.next;
node = node.next;
}
this.length--;
};if 조건에서 예외처리할 때 살짝 헷갈렸던 부분이 현재 연결 리스트의 길이 이상인 값이 들어왔을 때 return 시켜야 하는데 초과로 해놓는 바람에 길이보다 + 1 더 큰 값이 removeIndex로 들어온 경우 마지막에 위치한 노드가 삭제되는... 버그가 있었다. ㅋㅋㅋ
또 만들어보니 쉽네~ 했는데 예외처리나 범위를 생각 안한 부분이 많아서 쉬웠던 것이었다..ㅋㅋㅋ
그냥 설렁설렁 만드는 것보다 예외처리, 범위 조정하는 코드를 추가하고 수정하는데 더 오래 걸렸다.
그래도 처음 만든 허술한 연결 리스트에 비하면 많이 개선된 것 같다...ㅎㅎ
다음엔 미리미리 예외 상황부터 떠올리면서 코드를 작성하도록 해봐야 겠다.
