단방향 연결 리스트
배열은 값들 마다 위치 정보 즉 인덱스가 있다.
단방향 연결 리스트는 인덱스가 없다. 그냥 다음 데이터를 가리키는 값들의 집합이다.
마치 기차처럼. 데이터에 접근하기 위한 인덱스가 없기 때문에 몇번째 값에 바로 접근 못한다. 항상 처음(head)부터 타고 들어가야 한다.
각각의 엘리먼트를 ‘node’라고 부른다.
각 노드들은 다음 노드를 가리키는 정보를 저장하며 다음 노드가 없을 경우 null을 저장한다.
‘head’는 연결 리스트의 시작 노드를 가리킨다.
‘tail’은 연결 리스트의 마지막 노드를 가리킨다.
‘length’는 연결 리스트의 길이를 저장한다.
엘리베이터가 없는 고층 건물과 같다. 무조건 1층부터 올라가야함.
‘next’ 포인터에 다음 노드를 저장. 이것으로 연결되어 있다.
코드 스타터 & push 메소드
class Node{
constructor(val){
this.val = val; // 새로운 노드를 만들면 값은 val이 되고
this.next = null; // next 포인터는 null이 됨.
}
}
class SinglyLinkedList{
constructor(){ // 새로 만들면 실행되는 생성자 함수.
this.head = null; // 헤드와 테일과 길이가 선언됨.
this.tail = null;
this.length = 0;
}
push(val){
var newNode = new Node(val); // 위에서 만든 Node 클래스 사용.
if(!this.head){ // 헤드가 없으면. 즉 아직 아무것도 없으면
this.head = newNode;
this.tail = this.head; // 헤드와 테일 모두 새로 넣는 노드로.
} else {
this.tail.next = newNode; // 지금 현재 테일 뒤에 새로운 노드.
this.tail = newNode; // 테일을 바꿈.
}
this.length++; // 길이가 1 늘어나고
return this; // 그것을 반환.
}
}
var list = new SinglyLinkedList()
// list.push("HELLO")
// list.push("GOODBYE")단방향 연결리스트 메소드
pop()
맨 뒤에 있는 노드를 제거한다.
pop(){
if(!this.head) return undefined; //헤드가 없다면(빈 리스트라면) 언디파인드 리턴.
var current = this.head; // 커렌트는 헤드부터 시작.
var newTail = current; // 새로운 테일은 커렌트.
while(current.next){ // next가 있다면. 즉 마지막 노드가 아니라면
newTail = current; // newTail -> current 순으로 계속 이동
current = current.next;
} // 끝까지 돌면 맨 마지막 노드는 current, 그 전 노드는 newTail.
this.tail = newTail; // tail을 마지막 전 노드. newTail로 바꿈.
this.tail.next = null; // next를 null로 한다. 즉 마지막 값과 연결을 끊는다.
this.length--; // 길이는 1 줄임.
if(this.length === 0){ // 만약 pop을 해서 빈 리스트가 되면
this.head = null;
this.tail = null;
}
return current; // 뺀 값을 리턴.
}shift()
맨 앞에 노드를 제거. 간단하다. 아주 빨리 가능.
shift(){
if(!this.head) return undefined; // 빈 리스트이면
var currentHead = this.head; // 현재 헤드를 헤드로 잡고
this.head = currentHead.next; // 헤드를 현재 헤드의 다음 노드로 바꿈.
this.length--; // 길이를 1 줄인다.
if(this.length === 0){ // 빈 리스트가 되면
this.tail = null;
}
return currentHead; // 처리한 값을 리턴.
}unshift()
리스트의 맨 앞에 새로운 값을 추가. 이것도 매우 빠르게 가능하다.
unshift(val){
var newNode = new Node(val);
if(!this.head) {
this.head = newNode;
this.tail = this.head;
} else {
newNode.next = this.head;
this.head = newNode;
}
this.length++;
return this;
}get()
인덱스, 혹은 위치를 의미하는 숫자를 인자로 받아서 해당 위치의 노드를 반환.
그런데 단방향 연결 리스트는 인덱스가 따로 없다. 즉 리스트의 첫번째(head)부터 순서대로 따라가야 함.
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()
인덱스와 고칠 값을 받아 값을 수정.
앞에서 만든 get()을 이용한다.
set(index, val){
var foundNode = this.get(index); //앞에 만든 get메소드로 해당 노드를 찾고
if(foundNode){ // 해당 노드가 있다면
foundNode.val = val; // 그 노드의 값은 주어진 인자 val로 대체
return true; // true를 리턴.
}
return false; // 해당 노드가 없다면 false 리턴.
}insert()
인덱스와 값을 받아 중간에 삽입함.
insert(index, val){
if(index < 0 || index > this.length) return false; //인덱스가 유효한지 검사
if(index === this.length) return !!this.push(val); // 맨 마지막에 삽입이라면 push와 같음. !!은 true를 리턴하게 하는 기능.
if(index === 0) return !!this.unshift(val); // 빈 리스트라면 unshift와 같음.
var newNode = new Node(val); //새로운 노드를 생성하고
var prev = this.get(index - 1); //삽입하는 지점보다 한칸 앞 노드
var temp = prev.next; // 한칸 앞 노드의 next 노드를 temp로 지정.
prev.next = newNode; // 한칸 앞 노드의 next 노드를 새로 만든 노드로 지정.
newNode.next = temp; // 새로 만든 노드의 next를 temp로 지정.
this.length++; // 길이를 1 늘인다.
return true;
}remove()
특정 위치의 노드를 삭제함
remove(index){
if(index < 0 || index >= this.length) return undefined; //인덱스 유효성 검사
if(index === 0) return this.shift(); //맨 앞 노드를 삭제하는 건 shift와 같음.
if(index === this.length - 1) return this.pop(); //맨 뒤 노드를 삭제하는건 pop과 같음
var previousNode = this.get(index - 1); // 삭제하려는 노드의 한칸 앞 노드를 지정
var removed = previousNode.next; //한칸 앞 노드의 next를 removed로 지정
previousNode.next = removed.next; //한칸 앞 노드의 next를 removed의 next로 지정. 즉 중간을 건너 뛰어버림.
this.length--; // 길이는 1 줄이고
return removed; //removed를 반환.
}reverse()
주어진 연결 리스트의 노드 순서가 역으로 연결되어야 함.
조금 복잡해서 면접 단골 소재.
reverse(){
var node = this.head; //노드를 헤드로 선언.
this.head = this.tail; // 헤드를 테일로 바꿈.
this.tail = node; // 테일은 노드로 바꿈. 즉 처음의 헤드가 테일이 됨.
var next;
var prev = null; // prev의 초기값은 맨 앞에 아무것도 없기 때문에 null. 리스트의 끝, tail의 next가 null이기 때문이다.
for(var i = 0; i < this.length; i++){ // 리스트의 길이만큼 반복된다.
next = node.next; //next는 node(맨 처음 head)의 next가 된다.
node.next = prev; // 그리고 node의 next는 prev이 된다.
prev = node; // prev은 node가 된다.
node = next; // node는 next가 된다.
}
// a -> b -> c -> d
// node
// next
// null <- a
// prev
// node
// next
// null <- a <- b
// prev
// node
// 이렇게 반복.
return this;
}Singly Linked Lists의 Big-O 복잡도
insertion - O(1)
removal - O(1) or O(n) 맨앞에 있다면 또는 맨 뒤에 있다면
searching - O(n)
access - O(n)
정리하면, 단방향 연결 리스트는 삽입과 삭제에서 배열(array)에 비해 우수하다.
따라서 삽입 혹은 삭제 작업을 주로하거나, 임의 접근 작업이 필요 없다거나 주어진 순서대로 데이터를 관리할 필요가 있다던가, 몇번째 노드에 접근할 필요가 없다면 단방향 연결 리스트가 적합하다.
→ 삽입과 삭제 시간이 중요하고 임의 접근에 대한 필요성이 별로 없을 경우!
Developer