Created
October 1, 2023 16:28
-
-
Save 0xabdulkhaliq/99a0fec28e4e986ab34ed9d1ee033549 to your computer and use it in GitHub Desktop.
Implementing Singly Linked-List using JavaScript
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Node { | |
constructor(value) { | |
this.value = value || null; | |
this.next = null; | |
} | |
} | |
class LinkedList { | |
constructor(head) { | |
this.head = head || null; | |
} | |
prepend(value) { | |
let tmp = null; | |
if (this.head !== null) tmp = this.head; | |
this.head = new Node(value); | |
this.head.next = tmp; | |
} | |
append(value) { | |
let tmp = this.head; | |
while (tmp.next !== null) tmp = tmp.next; | |
tmp.next = new Node(value); | |
} | |
size() { | |
let count = 0; | |
let tmp = this.head; | |
while (tmp !== null) { | |
tmp = tmp.next; | |
count++; | |
} | |
return count; | |
} | |
getHead() { | |
return this.head; | |
} | |
getTail() { | |
let tmp = this.head; | |
while (tmp.next !== null) tmp = tmp.next; | |
return tmp; | |
} | |
at(index) { | |
let tmp = this.head; | |
for (let i = 0; i < index; i++) { | |
tmp = tmp.next; | |
if (tmp === null) return "There is no item for this Index"; | |
} | |
return tmp; | |
} | |
pop() { | |
let cur = this.head; | |
let prev = null; | |
while (cur.next !== null) { | |
prev = cur; | |
cur = cur.next; | |
} | |
prev.next = null; | |
} | |
contains(value) { | |
let tmp = this.head; | |
while (tmp.next !== null) { | |
if (tmp.value === value) return true; | |
tmp = tmp.next; | |
} | |
return false; | |
} | |
find(value) { | |
let tmp = this.head; | |
for (let i = 0; i < this.size(); i++) { | |
if (tmp.value === value) return i; | |
tmp = tmp.next; | |
} | |
return null; | |
} | |
toString() { | |
let tmp = this.head; | |
let string = ""; | |
while (tmp !== null) { | |
string += `( ${tmp.value} ) -> `; | |
tmp = tmp.next; | |
} | |
return (string += "null"); | |
} | |
insertAt(value, index) { | |
if (this.head === null || index === 0) return this.prepend(value); | |
let cur = this.head; | |
let prev = null; | |
for (let i = 0; i < index; i++) { | |
prev = cur; | |
cur = cur.next; | |
if (cur === null) break; | |
} | |
const newNode = new Node(value); | |
prev.next = newNode; | |
newNode.next = cur; | |
} | |
remove(index) { | |
if (this.head === null) return "List is Empty!"; | |
if (index === 0) return (this.head = this.head.next); | |
let cur = this.head; | |
let prev = null; | |
for (let i = 0; i < index; i++) { | |
prev = cur; | |
cur = cur.next; | |
} | |
prev.next = cur.next; | |
} | |
} | |
/* | |
TESTING | |
*/ | |
const head = new Node(1) // Head Node | |
const list = new LinkedList(head) // Creating a Linked List | |
list.append(8) // Adds 8 at the end of Linked List | |
list.prepend(7) // Adds 8 at the starting of Linked List | |
list.size() // 3 | |
list.getHead() // Node { value: 7, next: Node {...}} | |
list.getTail() // Node { value: 8, next: null } | |
list.at(1) // Node { value: 1, next: Node { value: 8, next: null } } | |
list.pop() // 8 is popped out from List | |
list.pop() // 1 is also popped out now. | |
list.contains(7) // true | |
list.contains(8) // false, because we popped it earlier. | |
list.append(4) // Adding some more nodes.. | |
list.append(7) | |
list.find(4) // 4's Index is 1 | |
list.insertAt(1, 2) // 1 has been inserted between 1 & 3 | |
list.insertAt(7, 0) // 7 has been inserted at beginning of List | |
list.remove(1) // 7 has been removed from Index 1 | |
list.toString() // ( 7 ) -> ( 4 ) -> ( 1 ) -> ( 7 ) -> null |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Features
append(value)
adds a new node containing value to the end of the list or to start if list is emptyprepend(value)
adds a new node containing value to the start of the listsize()
returns the total number of nodes in the listgetHead()
returns the first node in the listgetTail()
returns the last node in the listat(index)
returns the node at the given index or error message if there is no node in the requested indexpop()
removes the last element from the listcontains(value)
returns true if the passed in value is in the list and otherwise returns falsefind(value)
returns the index of the node containing value, or null if not foundinsertAt(value, index)
inserts a new node with the provided value at the given index or at the end of the list if index is bigger than list sizeremoveAt(index)
removes the node at the given index or error message if the list is empty or if the request index is bigger than list sizetoString()
returns your LinkedList objects as strings in the format:( value ) -> ( value ) -> ( value ) -> null