1. 단일 연결 리스트 (Single Linked List)
연결 리스트란
데이터를 저장하는 자료구조로, 배열과 같이 순서에 따라 다수의 데이터를 담는다. 그러나 가장 큰 차이점이 있다면, 요소 각각의 인덱스가 존재하지 않는다. 튜플과 유사한 듯.
연결 리스트에서는 각각으 요소들을 노드(Node)라고 부른다. 각각의 노드는 문자열 혹은 숫자와 같은 하나의 데이터 엘리먼트를 저장한다. 추가로 다음 노드를 가리키는 정보(포인터, Pointer)를 저장하고 있어야 하며, 다음 노드가 더 이상 없을 경우 Null을 저장하게 된다.
연결 리스트에는 세 가지 속성이 존재하는데, 가장 앞단 노드인 헤드(Head), 말단 노드인 테일(Tail), 리스트의 길이(Length)를 통해 데이터를 관리한다. 인덱스가 존재하지 않기 때문에, 특정 노드에 접근하기 위해서는 헤드부터 다음 노드를 거쳐 가며 도달하게 된다.
연결 리스트는 배열에 비해 삽입과 제거가 용이하다. 임의 접근이 필요하지 않는 아주 긴 데이터셋에서 특이 강점을 보인다.
노드 클래스 셋업
// 1. 연결 리스트는 노드들의 집합이다.
// 2. 노드는 단일 데이터 항목을 저장하며
// 호출될 다음 노드들에 대한 참조 정보인 Next를 저장한다.
class Node {
constructor(val) {
this.val = val;
this.next = null;
}
}
var first = new Node("Hi");
first.next = new Node("there");
first.next.next = new Node("How");
first.next.next.next = new Node("Are You?");
>> 실제로 이렇게 사용하지는 않고, Push를 이용한다.
2. 구현 메서드
Push 메서드
연결 리스트 내부 메서드로, 이용자가 새로운 값을 Push할 경우 새로운 노드를 생성하여 값을 노드에 담는다. 이는 제일 말단에 위치하므로 해당 노드를 리스트의 Tail로 갱신해주어야 한다. 만약 빈 리스트일 경우, 해당 노드가 Head와 Tail 성질을 모두 갖게 된다. 마지막으로 이전 노드의 Next가 새로 생성된 노드를 가리키게 한다. Length도 1 증가시킨다.
class SinglyLinkedList {
constructor() {
this.head = null;
this.tail = null;
this.length = 0;
}
push(val) {
var newNode = new Node(val);
if (!this.head) {
// 리스트가 비어 있는 경우
this.head = newNode;
this.tail = this.head;
} else {
// 리스트가 비어 있지 않은 경우
this.tail.next = newNode;
this.tail = newNode;
}
this.length++;
return this;
}
}
Pop 메서드
마지막 노드, 즉 테일을 반환한다. 문제는 이를 제거하고 직전 노드를 새로운 테일로 갱신해야 하는데, 역방향 포인터를 갖고 있지 않기 때문에 처음부터 리스트를 계속 따라가야만 한다. 이를 어떻게 구현할지 생각해볼 필요가 있다.
Tail 직전의 노드를 찾기 위해 헤드부터 .next가 존재하는 한 반복적으로 노드를 타고 들어간다. For 반복문이나, 무한 루프를 사용할 수 있다.
의사코드
- 어떠한 입력도 받지 않는 Pop 메서드를 선언한다. 빈 리스트라면, undefined를 반환한다.
- this.head를 초기값으로 갖는 Current 변수를 선언하였다. Tail에 도달할 때까지 Head부터 노드를 타고 들어간다.
- 끝에서 두 번째 노드의 .next를 Null로 지정한다. (말단 노드와의 연결이 끊어지게 된다)
- 끝에서 두 번째 노드를 Tail로 갱신한다.
- 리스트 길이를 1 감소시킨다.
- 제거된 말단의 노드 값을 반환한다.
pop() {
// 빈 리스트일 경우 처리
if (!this.head) return undefined;
// Previous = newTail
// newTail은 current 직전 노드를 가리킨다.
var current = this.head;
var previous = current;
// current 다음 노드가 존재하는 한 루프가 계속 실행된다.
while (current.next) {
previous = current;
current = current.next;
}
// 루프가 완료된 시점에서, tail에는 제거될 끝단 노드가,
// previous에는 끝단 직전의 노드가 저장되어 있음
this.tail = previous;
this.tail.next = null;
this.length -= 1;
return current;
}중복되는 코드라 포함시키지 않았지만, 해당 메서드는 SingleLinkedList 클래스 내부 메서드로 존재한다.
Shift 메서드
리스트 제일 앞의 원소를 제거하는 메서드로, Pop 메서드보다 간결하다. 현재 헤드가 가리키고 있는 노드를 제거한 후, 다음 노드를 헤드로 갱신하는 것을 의미한다.
의사코드
- 마찬가지로 빈 리스트인 경우 (!this.head) undefined를 반환한다.
- .head를 현재 .head의 .next 노드로 갱신한다.
- 리스트 길이를 1 감소시킨다.
- 제거된 노드를 반환한다.
shift() {
if (!this.head) return undefined;
var currentHead = this.head;
this.head = currentHead.next;
this.length -= 1;
return currentHead;
}
Unshift 메서드
Push 메서드와 같이 새로운 노드를 리스트에 추가하는 방법이다. 새로 추가되는 노드를 Head로 갱신하고, 이 새로운 Head의 .next가 원래의 Head를 가리키게 하면 된다. 빈 리스트일 경우 Undefined를 반환하는 것이 아닌 Head와 Tail을 newNode로 지정해준다.
unshift(val) {
var newNode = new Node(val);
var currentHead = this.head;
if (!this.head) {
this.head = newNode;
this.tail = this.head;
} else {
this.head = newNode;
this.head.next = currentHead;
}
this.length += 1;
return this;
}
Get 메서드
인덱스 혹은 주어진 위치를 인자로 입력받아, 해당 위치에 있는 노드를 반환하는 메서드이다. 인덱싱 시 항상 Head에서 시작해야 하기 때문에, 주어진 인자 값만큼 리스트를 따라간 후 해당 위치의 노드를 반환한다.
인덱스가 음수이거나, 리스트의 길이와 같거나 더 클 경우의 예외 처리가 필요하다. 구현은 .next 변수를 추적하여 counting하기를 권장하는 바.
get(idx) {
var counter = 0;
var current = this.head;
if (idx < 0 || idx >= this.length) return null;
while (counter !== index) {
current = current.next;
counter += 1;
}
return current;
}
Set 메서드
위치 혹은 인덱스와 갱신 값을 입력받고, 해당 위치에 있는 노드를 해당 값으로 변경하는 메서드이다. Get 메서드를 활용해 해당 인덱스 값을 참조, 변경하며 변경 여부를 Boolean 값으로 반환받는다.
set(idx, value) {
var foundNode = this.get(idx);
if (foundNode) {
foundNode.val = val;
return true;
}
return false;
}
Insert 메서드
주어진 위치에 있는 노드를 밀어내고, 새로 입력받은 값을 저장한다.
의사코드
- 예외 처리 : 입력받은 인덱스가 음수이거나, 리스트의 길이보다 큰 경우 Null 반환
- 인덱스와 리스트의 길이가 동일하다면 제일 마지막 노드에 입력 값을 추가 (=Push). 제일 앞 노드의 경우에도 동일 (=Unshift)
- Get 메서드를 통해 원하는 인덱스의 노드를 반환받을 수 있는데, 뒤로 밀기 위해선 인덱스 - 1 위치에 존재하는 노드를 찾아야 함. (get(index-1))
- get(index-1)을 통해 찾은 노드의 Next에 새 노드를 연결하고, 새 노드의 Next에 밀린 노드를 연결해준다.
- 리스트의 길이를 1 증가시키고, 해당 메서드가 성공했을 경우 True, 실패했을 경우 False를 반환한다.
insert(idx, value) {
if (idx < 0 || idx > thisl.length) return false;
if (idx === this.length - 1) return !!this.push(value);
if (idx === 0) return !!this.unshift(value);
var newNode = new Node(val);
var prev = this.get(idx - 1);
var temp = prev.next;
// newNode와 prev 연결
prev.next = newNode;
newNode.next = temp;
this.length += 1;
return true;
}
해당 코드에서 눈여겨볼 지점은 return !!this.... 부분인데, 메서드의 결과를 일관성 있게 반환받기 위해 다른 메서드를 호출하여 실행한 후 그에 따른 결과 또한 Boolean 값으로 반환받았다. 강한 부정은.. 긍정
Remove 메서드
인덱스 혹은 위치 인자를 입력받아 해당 위치에 있는 노드의 연결을 끊어준다. 그러기 위해선 Prev 노드도 함께 저장되어야 할 듯 하다. 입력 예외 처리는 Insert 메서드와 동일.
remove(idx) {
if (idx < 0 || idx > thisl.length) return false;
if (idx === this.length - 1) return !!this.pop(value);
if (idx === 0) return !!this.shift(value);
var prev = this.get(idx - 1);
var removed = prev.next;
prev.next = removed.next;
this.length -= 1;
}
Reverse 메서드
리스트의 순서를 역으로 바꿔주는 메서드. 그냥 Tail부터 역으로 Next를 지정해주면 되지 않느냐 싶겠지만, SLL은 Head부터 노드를 찾아 들어간다는 것을 잊지말자.
기존의 Head를 Tail로 변경한다. Next를 서로 바꿔주는데, 그 다음 노드 또한 별도 변수에 임의로 저장해두어야 한다. 사용되는 변수들이 많고 이름도 비슷하기 때문에 혼동에 유의하자.
reverse() {
var node = this.head;
this.head = this.tail;
this.tail = node;
var next;
var prev = null;
for (var i = 0; i < this.length; i++) {
next = node.next;
node.next = prev;
node = next;
}
return this
}