단일 연결리스트
Last updated
Last updated
reference: 출처
linked list 란?
head(linked list의 시작 node), tail(마지막 node), length를 가지고 있는 자료구조
다음 데이터 element를 가리키는 index없이(접근할 index 없음), 다수의 data element(node)로 구성
각 node는 value와 pointer를 가지고 있고 string 혹은 number 형태로 저장
각 node는 다음 node를 가리키는 정보 역시 저장하고 있어야 하며, 다음 node가 없을 경우, null이 저장
head node → second node → third node를 알아내는 식으로 마지막 node까지 접근. 따라서 특정 node에 접근하고 싶다면 head node부터 시작
삽입과 제거를 쉽게 할 수 있다
연결리스트 vs 배열
배열
정적
좋음
안 좋음
좋음
O(1)
연결리스트
동적
안 좋음
좋음
안 좋음
O(n)
배열은 10층으로 바로 갈 수 있는 엘리베이터
연결리스트는 10층까지 순서대로 걸어 올라가야 한다.
**push
메서드**
class Node {
constructor(val) {
this.val = val;
this.next = null;
}
}
class SinglyLinkedList {
constructor() {
this.head = null;
this.tail = null;
this.length = 0;
}
push(val) {
let newNode = new Node(val);
// head가 없다면 새로운 node를 head, tail로 할당
if (!this.head) {
this.head = newNode;
this.tail = this.head;
// head가 있다면 새 node를 tail의 다음 list로 할당
} else {
this.tail.next = newNode;
this.tail = newNode;
}
// list의 length
this.length += 1;
return this;
}
}
const list = new SinglyLinkedList();
// list.push(1)
// > SinglyLinkedList {head: Node, tail: Node, length: 1}
// list.head
// > Node {val: 1, next: null}
// list.tail
// > Node {val: 1, next: null}
// list.push(10)
// > SinglyLinkedList {head: Node, tail: Node, length: 2}
// list.tail
// > Node {val: 10, next: null}
// list.head.next
// > Node {val: 10, next: null}
// 현재 list는 1 - 10 의 형태
pop
메서드
pop() {
if (!this.head) return undefined;
let current = this.head;
let newTail = current;
// 현재 node의 next node가 있을 때까지 반복
while (current.next) {
// 다음 node가 있다면
// 현재 node를 newTail로 할당
newTail = current;
// 현재 node의 next를 현재 node로 할당
current = current.next;
}
// 다음 node가 없다면 newTail을 this.tail에 할당
this.tail = newTail;
// this.tail의 다음 node를 null로 설정함으로써
// 1. 이후에 아무것도 없다고 알려주고
// 2. '!'에 대한 연결을 끊는다
this.tail.next = null;
this.length--;
// head만 남은 상황에서 pop 메서드를 사용하면 head, tail 모두 null
if (this.length === 0) {
this.head = null;
this.tail = null;
}
return current;
}
// pop 메서드
// list.pop()
// > Node {val: '!', next: null}
// list.pop()
// > Node {val: 'goodbye', next: null}
// list.pop()
// > Node {val: 'hello', next: null}
// list.pop() undefined
shift
메서드
shift() {
// head가 없으면 return
if (!this.head) return undefined;
// 현재 head를 currentHead로 할당
let currentHead = this.head;
// currentHead의 다음 node를
this.head = currentHead.next;
this.length--;
if (this.length === 0) {
this.tail = null;
}
return currentHead;
}
// shift 메서드
// list.shift()
// Node {val: 'hello', next: Node}
// list
// > SinglyLinkedList {head: Node, tail: Node, length: 2}head: Node {val: 'goodbye', next: Node}length: 2tail: Node {val: '!', next: null}[[Prototype]]: Object
// list.shift()
// > Node {val: 'goodbye', next: Node}
// list
// > SinglyLinkedList {head: Node, tail: Node, length: 1}
unshift
메서드
unshift(val) {
// 새로운 node 생성
let newNode = new Node(val);
// head가 없으면 새 node를 head에 할당, 기존 head를 tail에 할당
if (!this.head) {
this.head = newNode;
this.tail = this.head;
}
// 현재 head를 새 node의 다음 node로 할당
newNode.next = this.head;
// 그리고 새 node를 현재 head로 할당
this.head = newNode;
this.length++;
// 전체 list return
return this;
}
// unshift 메서드
// list.unshift('first')
// > SinglyLinkedList {head: Node, tail: Node, length: 4}
// head: Node {val: 'first', next: Node}
// length: 4
// tail: Node {val: '!', next: null}
get
메서드
get(index) {
// index가 0보다 작고 또는 list 길이보다 크거나 같으면 null
if (index < 0 || index >= this.length) return null;
let counter = 0;
// list의 head를 current값으로 할당
let current = this.head;
// counter가 index값과 같지 않을때까지 '현재 node의 다음 node'를 current node에 할당하며 반복
while (counter !== index) {
current = current.next;
counter++;
}
return current;
}
// get 메서드
// list.get(-2)
// > null
// list.get(6)
// > null
// list.get(3)
// > Node {val: 'what', next: Node}
set
메서드
set(index, val) {
// get 메서드로 index를 찾고 foundNode에 할당
let foundNode = this.get(index);
// foundNode가 있으면 val값을 foundNode의 val값에 저장하고 true 반환 그렇지 않으면 false반환
if (foundNode) {
foundNode.val = val;
return true;
}
return false;
}
// set 메서드
// list.get(3)
// > Node {val: 'what', next: Node}
// list.set(3, 'oh')
// > true
// list
// > SinglyLinkedList {head: Node, tail: Node, length: 5}head: Node {val: 'hello', next: Node}length: 5tail: Node {val: 'the', next: null}[[Prototype]]: Object
// list.get(3)
// > Node {val: 'oh', next: Node}
// list.set(6, 'asdasd')
// > false
**insert
메서드**
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);
let newNode = new Node(val);
let prev = this.get(index - 1);
let temp = prev.next;
prev.next = newNode;
newNode.next = temp;
this.length++;
return true;
}
// 1. 입력한 index가 0보다 작거나 list 길이보다 크면 false
// 2. 입력한 index가 list의 길이와 같으면 list 끝에 새로운 node를 추가한다
// 3. 입력한 index가 0이면 새로운 node(val)를 list의 맨 앞에 unshift한다
// 4. 입력한 값의 node(val)를 newNode 변수에 할당한다
// 5. insert하려는 index를 찾기 위해서 get 메서드를 사용해 index - 1 값의 node를 prev 변수에 할당한다
// 6. val를 담을 node(prev.next)를 temp에 할당한다
// 7. 이 temp node를 새로 생성한 node의 next에 할당한다
const list = new SinglyLinkedList();
list.push(100);
list.push(201);
list.push(250);
list.push(350);
// insert
// list.insert(0, 'first');
// > SinglyLinkedList {head: Node, tail: Node, length: 5}
// list
// > SinglyLinkedList {head: Node, tail: Node, length: 5}head: Node {val: 'first', next: Node}length: 5tail: Node {val: 350, next: null}
// list.get(4)
// > Node {val: 350, next: null}
// list.insert(5, 'last')
// > SinglyLinkedList {head: Node, tail: Node, length: 6}head: Node {val: 'first', next: Node}length: 6tail: Node {val: 'last', next: null}
// list
// > SinglyLinkedList {head: Node, tail: Node, length: 6}head: Node {val: 'first', next: Node}length: 6tail: Node {val: 'last', next: null}
// list.get(5)
// > Node {val: 'last', next: null}
remove
메서드
특정 index의 node를 제거
remove(index) {
if (index < 0 || index >= this.length) return undefined;
if (index === 0) return this.shift();
if (index === this.length - 1) return this.pop();
let prev = this.get(index - 1);
let removed = prev.next;
prev.next = removed.next;
this.length--;
return removed;
}
// 1. 입력한 index값이 0보다 작거나 list 길이보다 크면 undefined
// 2. 입력한 index값이 0이면 shift메서드를 사용해 제거
// 3. 입력한 index값이 tail이면 pop메서드 사용해 제거
// 4. get메서드를 사용해 제거하려는 index 전의 node를 prev에 할당
// 5. prev의 다음 node를 removed(제거할) 변수에 할당
// 6. removed(제거할) node의 다음 node를 prev의 다음 node에 할당
// remove 메서드
// list.remove(0)
// > Node {val: 100, next: Node}
// list.remove(2)
// > Node {val: 350, next: null}