## DEV Community

``````                   -Intro to Singly Linked List
-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

``````

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;
}
}

constructor(){
this.tail = null;
this.length = 0;
}
push(val){
var newNode = new Node(val);
} else {
this.tail.next = newNode;
this.tail = newNode;
}
this.length++;
return this;
}
}

// list.push("HELLO")
// list.push("GOODBYE")

``````

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(){
var newTail = current;
while(current.next){
newTail = current;
current = current.next;
}

``````

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
Decrement the length by 1
Return the value of the node removed

``````
shift(){
this.length--;
if(this.length === 0){
this.tail = null;
}
}
}

``````

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

``````
unshift(val){
var newNode = new Node(val);
} else {
}
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;
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 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

``````

reverse(){
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;
}
}

constructor(){
this.tail = null;
this.length = 0;
}
push(val){
var newNode = new Node(val);
} else {
this.tail.next = newNode;
this.tail = newNode;
}
this.length++;
return this;
}
pop(){
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.tail = null;
}
return current;
}
shift(){
this.length--;
if(this.length === 0){
this.tail = null;
}
}
unshift(val){
var newNode = new Node(val);
}
this.length++;
return this;
}
get(index){
if(index < 0 || index >= this.length) return null;
var counter = 0;
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(){
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 = [];
while(current){
arr.push(current.val)
current = current.next
}
console.log(arr);
}
}

list.push(100)
list.push(201)
list.push(250)
list.push(350)
list.push(999)

``````