Created
June 21, 2022 07:55
-
-
Save alguerocode/3221bbe96ad6c0b9a769d32608806dfc to your computer and use it in GitHub Desktop.
understandable singly linked list in javascript
This file contains hidden or 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
// list node constructor | |
function ListNode(val) { | |
this.next = null; | |
this.value = val; | |
} | |
const MyLinkedList = function () { | |
this.head = null; // the head of the linked lsit | |
this.size = 0; // use the size to have addtional useful validation | |
}; | |
MyLinkedList.prototype.get = function (index) { | |
if (this.head == null || index >= this.size) return -1; | |
let cur = this.head; | |
while (index > 0) { | |
cur = cur.next; | |
index--; | |
} | |
return cur.value; | |
}; | |
MyLinkedList.prototype.addAtHead = function (val) { | |
// init the list node | |
const newNode = new ListNode(val); | |
if (this.head == null) { | |
this.head = newNode; | |
} else { | |
newNode.next = this.head; | |
this.head = newNode; | |
} | |
this.size++; | |
}; | |
MyLinkedList.prototype.addAtTail = function (val) { | |
const newNode = new ListNode(val); | |
if (this.head == null) this.head = newNode; | |
else { | |
let cur = this.head; | |
while (cur.next) cur = cur.next; | |
cur.next = newNode; | |
} | |
this.size++; | |
}; | |
MyLinkedList.prototype.addAtIndex = function (index, val) { | |
if (index < 0 || index > this.size) return; | |
const newNode = new ListNode(val); | |
if (index == 0 && this.head == null) { | |
this.head = newNode; | |
} else if (index == 0) { | |
newNode.next = this.head; | |
this.head = newNode; | |
} else { | |
let cur = this.head; | |
while (index > 1) { | |
cur = cur.next; | |
index--; | |
} | |
if (cur.next) { | |
newNode.next = cur.next; | |
} | |
cur.next = newNode; | |
} | |
this.size++; | |
}; | |
// delete at index | |
MyLinkedList.prototype.deleteAtIndex = function (index) { | |
// do some checks (valid enterd index, valid enterd index with the size, if there any elements) | |
if (index < 0 || index >= this.size || this.head == null) { | |
return; | |
} | |
else if (index == 0) { | |
this.head = this.head.next; | |
} | |
else { | |
// point to the head of the linked list | |
let cur = this.head; | |
// traversal the linked list until we find the the node is before the current index | |
while (index > 1) { | |
cur = cur.next; | |
index--; | |
} | |
// delete the current index | |
cur.next = cur.next.next; | |
} | |
// decrease the size | |
this.size--; | |
}; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
good