LinkedList:
A linked list is a linear data structure similar to an array. However, unlike arrays, elements are not stored in a particular memory location or index. Rather each element is a separate object that contains a pointer or a link to the next object in that list.
Advantages:
- Nodes can easily be added or removed from a linked list without re-organizing the entire data structure.
Disadvantages:
- Search operations are slow in linked list over arrays, random access of data element is not allowed. Nodes are accessed sequentially from first node.
- It uses more memory than arrays because of storage of the pointer.
Internal Design of linked list
function LinkedList() {
let length = 0;
let head = null;
const Node = function(element) {
this.element = element;
this.next = null;
}
this.size = function() {
return length;
}
this.head = function() {
return head;
}
this.add = function(element) {
let node = new Node(element);
if (head == null) {
head = node;
} else {
let currentNode = head;
while (currentNode.next) {
currentNode = currentNode.next;
}
currentNode.next = node;
}
length++
}
this.remove = function(element) {
let currentNode = head;
let previousNode;
if (currentNode.element == element) {
head = currentNode.next;
} else {
while (currentNode.element !== element) {
previousNode = currentNode;
currentNode = currentNode.next;
}
previousNode.next = currentNode.next;
}
length--;
}
this.isEmpty = function() {
return length == 0;
}
this.indexOf = function(element) {
let currentNode = head;
let index = -1;
while (currentNode) {
index++;
if (currentNode.element == element) {
return index;
}
currentNode = currentNode.next;
}
return -1;
}
this.elementAt = function(index) {
let currentNode = head;
let count = 0;
while (count < index) {
count++
currentNode = currentNode.next;
}
return currentNode.element;
}
}
var link = new LinkedList();
link.add("hello");
link.add("hello")
console.log(link)
console.log("elementAt", link.elementAt(0))
console.log("indexOf", link.indexOf("bye"))
link.remove("hello")
link.remove("hello")
console.log("isEmpty", link.isEmpty())
console.log("length", link.size())
Any comments or suggestions are welcome.
Top comments (0)