What is a linked list?
A data structure that contains a head, tail and length property.
Linked Lists consist of nodes, and each node has a value and a pointer to another node or null.
- head : the beginning of the linked list
- tail : the end of the linked list
- length : the number of nodes
Comparisons with Arrays
Array : 엘레베이터가 있는 빌딩 ( 5층으로 가주세요 → 한번에 가능)
- indexed in order
- Insertion and deletion can be expensive
- Can quickly be accessed at a specific index
Singly Linked List : 엘레베이터가 없는 빌딩 ( 계단을 통해 한층한층 옮겨다님 )
- Do not have indexes
- Connected via nodes with a next pointer
- Random access is not allowed
Linked List 는 Data 의 삽입(insertion)과 삭제(deletion)에 용이하다
Array가 추가와 삭제에 대해 O(n) , linear 복잡도를 갖는 반면, Linked List 는 O(1), constant 시간 복잡도를 갖는다.
단 , 특정 데이터를 연결리스트에서 검색하고자 할 경우, 처음부터 전체 리스트를 훑어야 하며, 이는 O(n) (linear complexity) 의 복잡도를 필요로 합니다.
keyword : 자료의 추가, 삭제를 용이하게 하기 위함.
자원의 사용량 측면에서는 array가 더 효율적임 (linked list는 next 포인터까지 주어져야하므로 ..)
Method
기본세팅
class Node {
constructor(val) {
this.val = val;
this.next = null;
}
}
class SinglyLinkedList {
constructor() {
this.length = 0;
this.head = null;
this.tail = null;
}1. push
Pushing pseudocode
- This function should accept a value
- Create a new node using the value passed to the function
- If there is no head property on the list, set the head and tail to be the newly created node.
- Otherwise set the next property on the tail to be the new node and set the tail property on the list to be the newly created node.
- Increment the length by one
push(val){
const newNode = new Node(val);
if (!this.head) {
this.head = newNode;
this.tail = this.head;
} else {
this.tail.next = newNode;
this.tail = newNode;
}
this.length += 1;
return this;
}2. pop
Popping pseudocode
- If there are no nodes in the list, return undefined
- Loop through the list until you reach the tail
- Set the next property of the 2nd to last node to be null
- Set the tail to be the 2nd to last node
- Decrement the length of the list by 1
- Return the value of the node removed
pop(){
if (!this.head) {
return undefined;
}
let current = this.head;
let newTail = current;
while(current.next) {
newTail = current;
current = current.next;
}
this.tail = newTail;
this.tail.next = null;
this.length -= 1;
if(this.length === 0) {
this.head = null;
this.tail = null;
}
return current;
}3. Shift
Shifting pseudocode
- If there are no nodes, return undefined.
- Store the current head property in a variable
- Set the head property to be the current head's next property
- Decrement the length by 1
- Return the value of the node removed
shift(){
if (!this.head) {
return undefined;
}
let currentHead = this.head;
this.head = currentHead.next;
this.length -= 1;
if(this.length === 0){
this.tail = null;
}
return currentHead;
}4. Unshift
Unshifting pseudocode
- This function should accept a value
- Create a new node using the value passed to the function
- If there is no head property on the list, set the head and tail to be the newly created node.
- Otherwise set the newly created node's next property to be the current head property on the list
- Set the head property on the list to be that newly created node
- Increment the length of the list by 1
- return the linked list
unshift(val){
let 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;
}5. Get
Retrieving a node by it's position in the Linked List!
Get pseudocode
- This function should accept an index
- If the index is less than zero or greater than or equal to the length of the list, return null.
- Loop through the list until you reach the index and return the node at that specific index
get(index){
if(index < 0 || index >= this.length) return null;
let counter = 0;
let current = this.head;
while (counter !== index) {
current = current.next;
counter++;
}
return current;
}6. Set
Changing the value of a node based on it's position in the Linked List
Set pseudocode
- This function should accept a value and an index
- Use your get function to find the specific node.
- If the node is not found, return false
- If the node is found, set the value of that node to be the value passed to the function and return true
set(index, value){
let foundNode = this.get(index);
if(foundNode) {
foundNode.val = value;
return true;
}
return false;
}7. Insert
Adding a node to the Linked List at a specific position
Insert pseudocode
- If the index is less than zero or greater than the length, return false
- If the index is the same as the length, push a new node to the end of the list
- If the index is 0, unshift a new node to the start of the list
- Otherwise, using the get method, access the node at the index -1
- Set the next property on that node to be the new node
- Set the next property on the new node to be the previous next
- Increment the length
- Return true
insert(index, value) {
if(index < 0 || index > this.length) {
return false;
}
if (index === this.length) {
return !!this.push(value);
}
if (index === 0) {
return !!this.unshift(value);
}
let newNode = new Node(value);
let prev = this.get(index -1);
let temp = prev.next;
prev.next = newNode;
newNode.next = temp;
this.length++;
return true;
}8. Remove
Removing a node from the Linked List at a specific position
Remove pseudocode
- If the index is less than zero or greater than the length, return undefined
- If the index is the same as the length-1, pop
- If the index is 0, shift
- Otherwise, using the get method, access the node at the index-1
- Set the next property on that node to be the next of the next node
- Decrement the length
- Return the value of the node removed
remove(index){
if(index < 0 || index > this.length) {
return undefined
}
if (index === this.length-1 ) {
return this.pop();
}
if (index === 0) {
return this.shift();
}
let previousNode = this.get(index-1);
let removed = previousNode.next;
previousNode.next = removed.next;
this.length--;
return removed;
}9. Reverse
Reversing the Linked List in place!
Reverse pseudocode
- Swap the head and tail
- Create a variable called next
- Create a variable called prev
- Create a variable called node and initialize it to the head property
- Loop through the list
- Set next to be the next property on whatever node is
- Set the next property on the node to be whatever prev is
- Set prev to be the value of the node variable
- Set the node variable to be the value of the next variable
reverse() {
let node = this.head;
this.head = this.tail;
this.tail = node;
let next;
let prev = null;
for (let i=0; i<this.length; i++) {
next = node.next;
node.next = prev;
prev = node;
node = next;
}
return this;
}Big O of Singly Linked List
Insertion - O(1)
Removal = It depends.. O(1) or O(n)
Searching - O(n)
Access - O(n)
Recap
- Singly Linked Lists are an excellent alternative to arrays when insertion and deletion at the beginning are frequently required
- Arrays contain a built in index whereas Linked Lists do not
- The idea of a list data structure that consists of nodes is the foundation for other data structures like Stacks and Queues
Frontend Developer