-Intro to Singly Linked List
-Singly Linked List: Push
-Singly Linked List: Pop
-Singly Linked List: Shift
-Singly Linked List: Unshift
-Singly Linked List: Get Intro
-Singly Linked List: Set Intro
-Singly Linked List: Insert Intro
-Singly Linked List: Remove Intro
-Singly Linked List: Reverse Intro
-Singly Linked List: BIG O Complexity
Intro to Singly Linked List
Linked List is a data structure that contains a head, tail and length property. Linked Lists consists of nodes, and each node has a value and a pointer to another node or null.
Always asking for the next item in the list.
A bunch of nodes pointing to other nodes.
Singly linked list are only connected in a single direction.
A fun resource to see algorithm and data structures
https://visualgo.net/en
Linked List Compared to Arrays
List
Do not have indexes
Connected via nodes with a next pointer
Random access is not allowed
Arrays
Indexed in order
Insertion and deletion can be expensive
Can quickly be accessed at a specific index
Singly Linked List: Push
The push() method adds new items to the end of an array and returns the new length.
Push Pseudocode
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
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;
}
}
var list = new SinglyLinkedList()
// list.push("HELLO")
// list.push("GOODBYE")
Singly Linked List: Pop
The pop() method removes the last element of an array and returns that element.
Pop 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;
var current = this.head;
var newTail = current;
while(current.next){
newTail = current;
current = current.next;
}
Singly Linked List: Shift
The shift() removes a new node from the beginning of the Linked List.
Shift 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 next property
Decrement the length by 1
Return the value of the node removed
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;
}
}
Singly Linked List: Unshift
The unshift() adds a new node to the beginning of the Linked List.
Unshift Pseudocode
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 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){
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;
}
}
Singly Linked List: Get Intro
The get() retrieves a node by its position in the Linked List.
Get Pseudocode
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;
var counter = 0;
var current = this.head;
while(counter !== index){
current = current.next;
counter++;
}
return current;
}
Singly Linked List: Set Intro
The set() changes the value of a node based on its position in the Linked List.
Set Pseudocode
Function should accept a value and an index
Use get function to find 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, val){
var foundNode = this.get(index);
if(foundNode){
foundNode.val = val;
return true;
}
return false;
}
Singly Linked List: Insert Intro
The insert() adds 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
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;
}
Singly Linked List: Remove Intro
The remove() removes 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 === 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;
}
Singly Linked List: Reverse Intro
The reverse() reveres the Linked List
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;
}
Final Code
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)
Top comments (0)