Singly Linked List - 단일 연결 리스트
목차
1. 단일 연결 리스트 소개
2. 코드 스타터와 push 메소드 소개
3. push 메소드 솔루션
4. pop 메소드 소개
5. pop 메소드 솔루션
6. shift 메소드 소개
7. shift 메소드 솔루션
8. unshift 메소드 소개
9. unshift 메소드 솔루션
10. get 메소드 소개
11. get 메소드 솔루션
12. set 메소드 소개
13. set 메소드 솔루션
14. insert 메소드 소개
15. insert 메소드 솔루션
16. remove 메소드 소개
17. remove 메소드 솔루션
18. reverse 메소드 소개
19. reverse 메소드 솔루션
20. 빅오 복잡도
참고
유튜브 연결 리스트 : https://www.youtube.com/watch?v=dvKuG3gfLFQ
1. 단일 연결 리스트 소개
슬라이드 : https://cs.slides.com/colt_steele/singly-linked-lists
visual : https://visualgo.net/en/list
목표
1. 단일 연결리스트 정의
2. 연결리스트와 배열을 비교, 대조
3. 삽입(insertion), 제거(removal), 순회(traversal) 메서드 적용
연결리스트란?
1. 머리(head), 꼬리(tail)와 길이 프로퍼티를 가진 자료 구조이다.
2. 연결리스트는 노드를 가지고있다. 각각의 노드는 값(value)과 다른 포인터(다른 노드 or null 가리키는)를 가지고 있다.
배열과 비교
Lists
- index가 없다.
- 다음 포인터를 가진 노드를 통해 연결되어 있다.
- 무작위 접근이 허용되지 않는다.
Arrays
- 순서대로 index가 주어져있다.
- 삽입과 삭제가 비용이 많이 든다.
- 특정 인덱스로 빠르게 접근할 수 있다.
2. 코드 스타터와 push 메소드 소개
pushing 은 연결리스트의 끝에 새 노드를 추가하는 것이다.
pushing 의사코드
- 이 함수는 값을 받아들인다.
- 함수로 전달된 값을 사용해서 새로운 노드를 만든다.
- 리스트에 head 프로퍼티가 없는 경우(비어있는 경우), head와 tail을 새로 만든 노드로 설정한다.
- 그렇지 않으면(비어있지 않다면) tail의 다음 프로퍼티를 새 노드로 설정하고, (현재의 tail을 리스트의 맨 끝으로 추가)
리스트의 tail 프로퍼티를 새로 생성된 노드로 설정한다. (tail의 marker를 마지막 노드로 가리킴)
- 길이를 1씩 늘린다.
- 연결 리스트를 리턴한다.
Code Starter
// piece of data - val
//reference to next node - next
class Node{
constructor(val){
this.val = val;
this.next = null;
}
}
class SinglyLinkedList{
constructor(){
this.head = null;
this.tail = null;
this.length = 0;
}
push(val){
// HERE
}
}
// var first = new Node("Hi")
// first.next = new Node("there")
// first.next.next = new Node("how")
// first.next.next.next = new Node("are")
// first.next.next.next.next = new Node("you")
var list = new SinglyLinkedList()
list.push("HELLO")
list.push("GOODBYE")3. 단일 연결 리스트 : push 메소드 솔루션
코드 실행 순서 확인 할것 : https://pythontutor.com/visualize.html#mode=edit
push 메소드
class SinglyLinkedList{
push(val){
var newNode = new Node(val);
if(!this.head){ // 리스트가 비어있는 특별한 케이스가 하나 있다.
this.head = newNode;
this.tail = this.head;
} else { // 비어있지 않을 경우 현재의 tail을 이용함
this.tail.next = newNode; // tail을 이용해서 리스트의 마지막에 새로운 노드를 추가하고
this.tail = newNode; // tail을 맨 끝을 가리키도록 한 자리 움직여 주면 됨
}
this.length++;
return this;
}
}
var list = new SinglyLinkedList()
// list.push("HELLO")
// list.push("GOODBYE")
4. 단일 연결 리스트 : pop 메소드 소개
pop() 을 호출하면 연결 리스트의 맨 마지막에서 노드를 제거한다.pop() 은 마지막 노드, 즉 tail을 반환하게 된다.
- 지금까지 마지막 노드인 tail을 추적해오고 있기 때문에 어쩌면 간단하게 보일 수도 있다.
문제는 그 마지막 노드를 제거해야 한다는 것이다.또한 tail이 새로운 마지막 노드를 가리키도록 해야 하는데
이것은 역방향 포인터를 가지고 있지 않기 때문에 처음부터 리스트를 계속 따라가야만 가능하다.
tail로부터 그 전 노드를 그냥 알아 낼 수는 없다. 단방향 연결 리스트가 동작하는 방식이 아니다.
- 먼저 해야할 것은 리스트를 따라가(traverse)는 작업이다.
(head를 이용해 처음부터 시작해서 .next가 존재하는 한 반복적으로 계속 따라가면 됨)
- 리스트의 마지막까지 계속 따라갈 필요는 없다. 마지막에서 두 번째 노드만 찾으면 되고, 굳이 어떤 것을 출력할 필요도 없다.
Popping 의사코드
1. 리스트에 아무 것도 없을 경우, 그냥 'undefined'를 반환한다.
리스트가 비어 있는지 확인하려면 'head'값이 'null'인지 혹은 길이가 '0'인자 확인하면 된다.
2. 리스트가 비어 있지 않는 경우, tail에 이를 때까지 전체 리스트를 따라간다.
tail에 이를 때까지 계속 따라가는 동시에, 이전 노드가 어떤 것이었는지를 항상 추적하고 있어야 한다.
3. 마지막에서 2번째 있는 노드의 next 프로퍼티를 null로 설정한다.
4. 마지막에서 2번째 있는 노드를 tail로 설정한다.
5. 리스트의 길이를 1만큼 줄인다.
6. 제거된 노드의 값을 반환한다.
5. 단일 연결 리스트 : pop 메소드 솔루션
pop 메소드
class SinglyLinkedList{
pop(){
if(!this.head) return undefined; // 1
var current = this.head;
var newTail = current;
while(current.next){ // 2 // 루프는 current가 더 이상 앞으로 나아갈 수 없을 때까지 반복
newTail = current; // newTail은 항상 current에 끌려가는 형상, newTail은 항상 current가 이전에 가리키던 것으로 설정(바로 전 노드)
current = current.next; // current는 앞으로 한 단계 나아감
}
this.tail = newTail; // 4 // 마지막에서 2번째 노드가 이제 tail노드임
this.tail.next = null; // 3 // 이 후에 아무것도 없다는 의미
this.length--; // 5
if(this.length === 0){ // 리스트에 하나의 노드만 남겨져 있다가 제거되었을 경우(혹은 head와 tail이 서로 같아 진다면)
this.head = null; // head와 tail이 null로 설정되어야 한다.
this.tail = null;
}
return current; // 6
}
}
var list = new SinglyLinkedList()
list.push("HELLO")
list.push("GOODBYE")
list.push("!")6. 단일 연결 리스트 : shift 메소드 소개
shift() 메소드는 연결 리스트의 앞에서 노드를 제거한다.
이는 현재 head가 가리키고 있는 노드를 제거한 후 head를 head가 가리키고 있던 list의 두 번째 노드를 가리키도록 한다는 의미이다.
list 맨 앞에서 제거되는 수 백만 개의 노드가 있을 수 있지만, index를 모두 다시 수정해야 하는 array와 비교할 때
list 길이와 관계 없이 항상 동일한 시간에 처리할 수 있다.
array의 경우 만일 수 백만 개의 노드가 존재한다면,
node를 제거할 때마다 물결 처럼 list를 따라가며 지속적으로 엄청난 index들을 계속 변경해야 한다.
shifting 의사코드
1. 노드가 없을 경우, 'undefined' 반환
2. 노드가 존재할 경우, 현재 head 프로퍼티를 변수에 저장
3. 현재 head 프로퍼티를 head 프로퍼티의 'next' 노드를 가리키키도록 함 (즉, 한 칸 이동)
4. 리스트의 길이를 1 감소
5. 제거된 이전 head 노드의 값 반환
7. 단일 연결 리스트 : shift 메소드 솔루션
shift 메소드
class SinglyLinkedList{
shift(){
if(!this.head) return undefined; // 1
var currentHead = this.head; // 2
this.head = currentHead.next; // 3
this.length--; // 4
if(this.length === 0){ // 맨 앞 head 제거할 때 길이가 0이면 tail을 null로 최신화
this.tail = null;
}
return currentHead; // 5
}
}
var list = new SinglyLinkedList()
list.push("HELLO")
list.push("GOODBYE")
list.push("!")
8. 단일 연결 리스트 : unshift 메소드 소개
unshift()는 새로운 노드를 list에 추가하는 방법이다.
그러나, push() 메소드와 달리, 이것은 list의 맨 앞에 노드를 추가하는 방법이다.
단방향 연결 리스트가 동작하는 방식으로 인하여 unshift는 매우 쉽다.
새로운 head를 list 앞에 추가하고, 새로운 head가 이전 head를 가리키게 하는 것이 전부이다.
unshift 의사코드
1. 노드를 인자로 받아 들이는 함수 정의
2. push() 경우와 마찬가지로 새로운 노드 생성
3. (head 유무 체크) head가 없는 경우, head와 tail 모두 새로운 노드를 가리키도록 설정
4. node가 이미 있는 경우, 새롭게 생성된 노드의 'next'를 현재의 head 값으로 설정하고
5. head가 새롭게 생성된 노드를 가리킴
6. list 길이를 1 증가
7. 마지막으로, 연결 리스트 반환
9. 단일 연결 리스트 : unshift 메소드 솔루션
unshift 메소드
<script>
class SinglyLinkedList{
unshift(val){ // 1
var newNode = new Node(val); // 2
if(!this.head) { // 3
this.head = newNode;
this.tail = this.head;
} else {
newNode.next = this.head; // 4
this.head = newNode; // 5
}
this.length++; // 6
return this; // 7
}
}
var list = new SinglyLinkedList()
list.push("HELLO")
list.push("GOODBYE")
list.push("!")
</script>array의 경우, 시작 지점에 새로운 노드를 추가하게 되면 array 전체의 index를 다시 수정해야 한다.
즉, 모든 array 노드들의 index를 새로 설정해야 하기 때문에, 바람직한 작업은 아니다.
10. 단일 연결 리스트 : get 메소드 소개
- get()은 index 혹은 위치를 의미하는 숫자를 인자로 받아서 주어진 위치에 있는 노드를 반환하는 메소드이다.
- '0'을 인자로 주면 첫 번째이기 때문에, head를 반환한다.
- 만약 '4'를 인자로 주게 되면, 5번째 노드를 반환해야 한다. (위치 index가 '0'부터 시작하기 때문)
- 중요한 점은 주어진 숫자 만큼 list를 따라간 후 해당 위치의 노드를 반환한다는 것이다.
- list에는 각 개별 노드와 일치하는 index가 존재하지 않는다.
예를 들어, 700번째 노드를 즉각적으로 반환할 수 없다.
맨 처음인 '0'부터 몇번 이동했는지 계속 추적하면서 주어진 숫자만큼 반복할 때까지 계속 '.next'로 이동해야 한다.
- 만약 항상 위치를 기준으로 무엇인가에 접근해야 한다면, array를 사용하는 것이 좋다.
get 의사코드
1. index를 인자로 받음.
2. (index의 범위에 따라 엣지 케이스발생) index가 음수거나 list의 길이보다 같거나 클 경우엔 동작하지 않음. 이땐 null반환.
3. 루프를 통해 index가 지정하는 위치에 이를 때까지 반복해서 이동, 해당 index 위치에 있는 노드 반환.
3-1. 이동한 횟수를 추적하는 counter 변수를 사용해서, while 루프 내부에서 '.next'를 반복하기를 권장.
3-2. 매번 이동할 때마다 'counter' 변수를 1 만큼 증가. 이러면 index가 5번 째든 10번 째든 그냥 그 값 반환하면됨.
11. 단일 연결 리스트 : get 메소드 솔루션
get 메소드
class SinglyLinkedList{
get(index){ // 1
if(index < 0 || index >= this.length) return null; // 2
var counter = 0;
var current = this.head;
while(counter !== index){ // 3
current = current.next; // 3-1
counter++; // 3-2
}
return current;
}
}
var list = new SinglyLinkedList()
list.push("HELLO")
list.push("GOODBYE")
list.push("!")
list.push("<3")
list.push(":)")
12. 단일 연결 리스트 : set 메소드 소개
set()은 1. 위치 or index 2. 해당 index에 위치한 노드를 업데이트할 값 등 두 개의 인자를 받아 들인다.
ex) list.set(1, "HELLO WORLD!") 라고 한다면, 인덱스로 주어진 '1'에 위치한 노드의 주어진 값을 "HELLO WORLD!"로 업데이트한다.
set() 의사코드
1 index와 업데이트할 값을 인자로 받는 함수 정의
2. 특정한 노드를 찾을 때 get 메서드 사용 (원하는 노드가 없을 경우, 역시 get()가 알아서 처리하게 될 것)
ex) '-10' 번째 노드를 업데이트 하기 원할 경우, get() 메서드는 찾은 노드 반환하게 되고,
반환된 노드의 값은 주어진 값으로 업데이트될 것임.
3. 만약 노드를 못 찾았다면, 'false' 반환
4. 만약 노드를 찾았다면, 해당 노드 값을 인자로 받아들인 값으로 업데이트하고 'true' 반환
13. 단일 연결 리스트 : set 메소드 솔루션
set 메소드
class SinglyLinkedList{
set(index, val){ // 1
var foundNode = this.get(index);// 2
if(foundNode){ // 4
foundNode.val = val;
return true;
}
return false; // 3
}
}
var list = new SinglyLinkedList()
list.push("HELLO")
list.push("GOODBYE")
list.push("!")
list.push("<3")
list.push(":)")
14. 단일 연결 리스트 : insert 메소드 소개
inset() 메소드는 두 개의 인자를 받아 들였던 set()과 같이 인덱스와 값을 인자로 받아 들인다.
하지만, 이미 존재하는 노드를 업데이트하는 대신, 'inset()'는 주어진 노드를 새롭게 삽입한다는 차이가 있다.
unshift()는 list 맨 앞에 노드 삽입, push()는 list 맨 뒤에 노드 삽입
insert()는 특정 위치 index에 새 노드 삽입하는 기능이다.
ex) 만약 index '2'를 지정하면, index '1' 위치에 있는 노드를 찾아 새로운 노드에 연결함.
새노드는 기존 index '2'에 있는 node 를 next로 연결
insert() 의사코드
1. index(위치) 와 value(바꿀 값)를 인자로 받아들임
2. 만약 index가 0보다 작거나 list 길이보다 클 경우(범위 벗어나면 삽입 불가), false 반환
3. (list 길이보다 크거나 같은 경우가 아님!!) index가 list 길이와 같을 경우에는, list의 맨 마지막에 삽입하면 되기 때문
3-1. 이 경우 이미 정의한 'push()' 활용. (즉, list 맨 마지막에 삽입하려면 insert() 말고 push() 재사용됨)
3-2. 마찬가지로 index가 0이면 (list 맨 앞에 새 노드 삽입하길 원하면) 'unshift()' 활용.
4. 만약 2번에서 true이고, 3번의 index가 list길이와 같지않고, 0도 아닐때
4-1. index가 3이라면, 먼저, '2'위치의 노드를 찾음. get() 호출. 대신 'index-1'로 호출해야 함.
4-2. 즉, index 위치에 있는 노드가 아니라 index보다 하나 전에 위치한 노드를 찾는 것임.
5. index-1 노드의 'next'가 새롭게 생성된 후 삽입되는 노드를 가리킴
6. 새 노드의 'next'를 이전의 'next' 노드로 연결
7. 길이 1 증가
8. true 반환 ( 항상 insert 메서드 성공하면 true, 실패하면 false 반환. push(), unshift()경우도 마찬가지! )
15. 단일 연결 리스트 : insert 메소드 솔루션
insert 메소드
class SinglyLinkedList{
insert(index, val){ // 1
if(index < 0 || index > this.length) return false; // 2
if(index === this.length) return !!this.push(val); // 3-1
if(index === 0) return !!this.unshift(val); // 3-2
var newNode = new Node(val);
var prev = this.get(index - 1); // 4-1
var temp = prev.next;
prev.next = newNode; // 5
newNode.next = temp; // 6
this.length++; // 7
return true; //8
}
}
var list = new SinglyLinkedList()
list.push(100)
list.push(201)
list.push(250)
list.push(350)16. 단일 연결 리스트 : remove 메소드 소개
remove()는 index를 인자로 받아서 해당 index에 있는 노드를 제거하고 주위에 있는 것들을 연결한다.
중간 index 노드 제거하려면, 직전 노드를 찾아야 한다.
그러기 위해 먼저, 이전 노드를 찾아서 그 노드의 '.next'를 제거되는 노드의 다음 노드에 연결해야 한다.
remove() 의사코드
1. index가 0보다 작거나 길이보다 크거나 같을 경우 'undefiend' 반환
2. 만약에 index가 길이-1 과 같을 경우, 마지막 노드 제거용으로 pop() 재사용
3. 만약에 index가 0일 경우엔, shift() 재사용
4. 두 경우 다 아니라면, insert() 처럼 get() 메소드 사용해서 remove 시킴
4-1. 이전 노드 찾기 위해 get(인덱스-1) 함
5. 이전 노드의 '.next'를 다음 노드의 '.next'로 바꿈(index값의 노드를 가리키는 pointer가 없어져서 사라진것 같은 효과)
6. 길이 1 감소
7. 제거된 노드의 값 반환
17. 단일 연결 리스트 : remove 메소드 솔루션
remove 메소드
class SinglyLinkedList{
remove(index){ // 0
if(index < 0 || index >= this.length) return undefined; // 1
if(index === 0) return this.shift(); // 3
if(index === this.length - 1) return this.pop(); // 2
var previousNode = this.get(index - 1); // 4-1
var removed = previousNode.next;
previousNode.next = removed.next; // 5
this.length--; // 6
return removed; // 7
}
}
var list = new SinglyLinkedList()
list.push(100)
list.push(201)
list.push(250)
list.push(350)
18. 단일 연결 리스트 : reverse 메소드 소개
reverse() 의사코드
1. head와 tail을 스왑
2. next라는 변수 생성
3. prev라는 변수 생성
4. node라는 변수 생성 & 현재의 head 값으로 초기화
5. list 루프 돌림
5-1. 현재 node의 '.next'를 node'의 '.next.next'로 설정하는 작업을 반복.
현재 node의 '.next'를 별도로 저장해 놓음으로써, 현재 node의 '.next'값을 다시 다른 값으로 설정했을 때
거기에 저장되어 있는 연결 정보가 손실되지 않도록 해야 한다는 것이다.
6. 현재 node의 '.next'를 이전에 바로 앞에 있던 노드를 가리키도록 설정
7. 마지막으로, 현재 node 값을 prev에 저장하고, node 변수에 '.next'값을 저장
19. 단일 연결 리스트 : reverse 메소드 솔루션
reverse 메소드
class SinglyLinkedList{
reverse(){
var node = this.head; // 1, 4
this.head = this.tail; // 1 - head와 tail 스왑
this.tail = node; // 1
var next; // 2
var prev = null; // 3 - 리스트의 끝인 tail의 '.next'가 null 이기 때문, 루프 진행됨에 따라 업데이트 됨
for(var i = 0; i < this.length; i++){ // 5
next = node.next; // 5-1
node.next = prev; // 5-1 - 처음엔 null,
prev = node; // 7
node = next; // 7
}
return this;
}
print(){ // 순수하게 reverse() 내부에서 어떤 일이 진행되는지 확인하는 용도
var arr = [];
var current = this.head
while(current){
arr.push(current.val)
current = current.next
}
console.log(arr);
}
}
var list = new SinglyLinkedList()
list.push(100)
list.push(201)
list.push(250)
list.push(350)
list.push(999)실행 순서
[100, 201, 250, 350, 999]
PREV NODE NEXT
100 -> null
-----------------------------------------
[100, 201, 250, 350, 999]
PREV NODE NEXT
201 -> 100 -> null
-----------------------------------------
[100, 201, 250, 350, 999]
PREV NODE NEXT
250 -> 201 -> 100 -> null
-----------------------------------------
[100, 201, 250, 350, 999]
PREV NODE NEXT
350 -> 250 -> 201 -> 100 -> null
-----------------------------------------
[100, 201, 250, 350, 999]
PREV NODE NEXT
999 -> 350 -> 250 -> 201 -> 100 -> null최종
class Node{
constructor(val){
this.val = val;
this.next = null;
}
}
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(){
if(!this.head) return undefined;
var current = this.head;
var newTail = current;
while(current.next){
newTail = current;
current = current.next;
}
this.tail = newTail;
this.tail.next = null;
this.length--;
if(this.length === 0){
this.head = null;
this.tail = null;
}
return current;
}
shift(){
if(!this.head) return undefined;
var currentHead = this.head;
this.head = currentHead.next;
this.length--;
if(this.length === 0){
this.tail = null;
}
return currentHead;
}
unshift(val){
var newNode = new Node(val);
if(!this.head) {
this.head = newNode;
this.tail = this.head;
}
newNode.next = this.head;
this.head = newNode;
this.length++;
return this;
}
get(index){
if(index < 0 || index >= this.length) return null;
var counter = 0;
var current = this.head;
while(counter !== index){
current = current.next;
counter++;
}
return current;
}
set(index, val){
var foundNode = this.get(index);
if(foundNode){
foundNode.val = val;
return true;
}
return false;
}
insert(index, val){
if(index < 0 || index > this.length) return false;
if(index === this.length) return !!this.push(val);
if(index === 0) return !!this.unshift(val);
var newNode = new Node(val);
var prev = this.get(index - 1);
var temp = prev.next;
prev.next = newNode;
newNode.next = temp;
this.length++;
return true;
}
remove(index){
if(index < 0 || index >= this.length) return undefined;
if(index === 0) return this.shift();
if(index === this.length - 1) return this.pop();
var previousNode = this.get(index - 1);
var removed = previousNode.next;
previousNode.next = removed.next;
this.length--;
return removed;
}
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;
prev = node;
node = next;
}
return this;
}
print(){
var arr = [];
var current = this.head
while(current){
arr.push(current.val)
current = current.next
}
console.log(arr);
}
}
var list = new SinglyLinkedList()
list.push(100)
list.push(201)
list.push(250)
list.push(350)
list.push(999)20. 단일 연결 리스트 : 빅오 복잡도
Insertion - O(1)
Removal - 맨앞: O(1) or 맨뒤: O(N)
Searching - O(N)
Access - O(N) ↔ array는 인덱스만 알면 O(1)임
회고
1. 삽입 작업과 리스트 맨 앞 노드의 제거 등이 빈번하게 사용될 경우, 단방향 연결 리스트는 배열의 훌륭한 대안이 됨.
2. 배열은 내장된 index를 가지고 있는 반면, 단방향 연결 리스트는 index를 가지고 있지 않다.
2-1. 단방향 연결 리스트는 다음 노드로 연결되는 참조 or 포인터를 갖는 노드들의 집합체다.
2-2. 단방향 연결 리스트에는 index 혹은 위치 정보가 없다. 따라서 index 통해서 쉽게 노드 접근 불가하다.
3. 왜 단방향 연결 리스트 사용해야하는가? 자료 구조에 대한 강의라는 것과 이론적인 교육에 목적이 있다.
3-1. 스택 or 큐 자료 구조를 구현하기 위해서는 단방향 연결 리스트에 대한 이해가 있어야 한다.