- 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.
- Node is the name of each element in the list. They contain two items: the data stored and a link to the next node. The data can be any valid data type.
- Head is the entry point to a linked list. The head is a reference to the first node in the linked list. The last node on the list points to null. If a list is empty, the head is a null reference.
- Nodes can easily be removed or added from a linked list without reorganizing the entire data structure. This is one advantage it has over arrays.
- Search operations are slow in linked lists. Unlike arrays, random access of data elements is not allowed. Nodes are accessed sequentially starting from the first node.
- It uses more memory than arrays because of the storage of the pointers.
- Singly Linked Lists - Each node contains only one pointer to the next node.
- Double Linked Lists - Each node contains two pointers, a pointer to the next node and a pointer to the previous node.
- Circular Linked Lists - Circular linked lists are a variation of a linked list in which the last node points to the first node or any other node before it, thereby forming a loop.
List Node Class
class ListNode {
constructor(data) {
this.data = data
this.next = null
}
}
Linked List Class
class LinkedList {
constructor(head = null) {
this.head = head
}
}
Create Linked List
let node1 = new ListNode(2)
let node2 = new ListNode(5)
node1.next = node2
let list = new LinkedList(node1)
console.log(list.head.next.data) //returns 5
- Size - This method returns the number of nodes present in the linked list.
size() {
let count = 0;
let node = this.head;
while (node) {
count++;
node = node.next
}
return count;
}
- Display - This method displays all the nodes in the list.
const ListFunctions = {
display: (linkedList) => {
items = [];
if (linkedList.head === null) {
return "The list is empty";
} else {
let currNode = linkedList.head;
while (currNode.next !== null) {
items.push(currNode.data);
currNode = currNode.next;
}
items.push(currNode.data);
}
return `Linked List Items: ${items.join("->")}`;
}
- isEmpty - This method checks to see if the list is empty without using the size() method.
isEmpty: (linkedList) => {
if (linkedList.head === null) {
return `This list is empty`;
}
return `There are items in this list`;
}
- Find - This method finds a node in the list.
find(item) {
let currNode = this.head;
if (!this.head) {
return null;
}
while (currNode.data !== item) {
if (currNode.next === null) {
return null;
} else {
currNode = currNode.next;
}
}
return currNode;
}
}
- Clear - This method empties out the list.
clear() {
this.head = null;
}
- Remove - This method removes a node from the list.
remove(item) {
if (!this.head) {
return null;
}
if (this.head.data === item) {
this.head = this.head.next;
return;
}
let currNode = this.head;
let previousNode = this.head;
while (currNode !== null && currNode.data !== item) {
previousNode = currNode;
currNode = currNode.next;
}
if (currNode === null) {
return;
}
previousNode.next = currNode.next;
}
- insertFirst - This method inserts a node into the first position of the linked list.
insertFirst(item) {
this.head = new _Node(item, this.head);
}
- insertLast - This method inserts a node into the last position of the linked list.
insertLast(item) {
if (this.head === null) {
this.insertFirst(item);
} else {
let tempNode = this.head;
while (tempNode.next !== null) {
tempNode = tempNode.next;
}
tempNode.next = new _Node(item, null);
}
}
- insertBefore - This method inserts a node before a targeted node in the linked list.
insertBefore(item, key) {
if (!this.head) {
return;
}
if (this.head.data === key) {
this.insertFirst(item);
return;
}
let currNode = this.head;
let previousNode = this.head;
while (currNode !== null && currNode.data !== key) {
previousNode = currNode;
currNode = currNode.next;
}
if (currNode === null) {
console.log(`key value not found`);
return;
}
previousNode.next = new _Node(item, currNode);
}
- insertAfter - This method inserts a node after a targeted node in the linked list.
insertAfter(item, key) {
if (!this.head) {
return;
}
if (this.head.data === key) {
this.insertFirst(item);
return;
}
let currNode = this.head;
let nextNode = this.head;
while (currNode !== null && currNode.data !== key) {
currNode = nextNode;
nextNode = nextNode.next;
}
if (currNode === null) {
console.log(`key value not found`);
return;
}
currNode.next = new _Node(item, nextNode);
}
- getLast - This method returns the last node of the linked list.
getLast() {
let lastNode = this.head;
if (lastNode) {
while (lastNode.next) {
lastNode = lastNode.next
}
}
return lastNode
}
- getFirst - This method returns the first node of the linked list.
getFirst() {
return this.head;
}
- findPrevious - This method returns the previous node before the item you are looking for in the linked list.
findPrevious: (linkedList, key) => {
if (linkedList.head === null) {
return null;
}
let prevNode;
let currNode = linkedList.head;
while (currNode.data !== key) {
prevNode = currNode;
currNode = currNode.next;
}
return `The previous node is ${prevNode.data}`;
}
In these drills, you'll practice creating a linked list, implementing its core, and some supplemental operations. You will also use your linked list to solve interview questions. Don't forget to assess the big O for each of these exercises. Start each problem by stating 1 or more sample inputs and outputs.
Write a linked list class and these core functions (insertFirst, insertLast, remove, find) from scratch.
- Write a function main. Within the function, using the linked list class above, create a linked list with the name SLL and add the following items to your linked list: Apollo, Boomer, Helo, Husker, Starbuck.
- Add Tauhida to the list.
- Remove squirrel from the list.
- Implement a function called insertBefore() in the class that inserts a new node before a given node containing a key.
- Implement a function called insertAfter() in the class that inserts a new node after a node containing the key.
- Implement a function called insertAt() that inserts an item at a specific position in the linked list.
- Add Athena before Boomer using your insertBefore() function.
- Add Hotdog after Helo using the insertAfter() method.
- Using the insertAt() method insert Kat in the 3rd position of the list.
- Remove Tauhida from the list.
Implement the following functions that operate on your linked list class. Note that these should be free functions instead of methods of the linked list class, so implement them outside the linked list class. Test each function using the list created in exercise 1.
- display: displays the linked list
- size: returns the size of the linked list
- isEmpty: finds if the list is empty or not (without using the size() function)
- findPrevious: finds the node before the item you are looking for
- findLast: returns the last node in the linked list
Analyze the following function (without running it in an IDE) to determine what problem it is trying to solve. What is the time complexity of this algorithm?
function WhatDoesThisProgramDo(lst) {
let current = lst.head;
while (current !== null) {
let newNode = current;
while (newNode.next !== null) {
if (newNode.next.value === current.value) {
newNode.next = newNode.next.next;
}
else {
newNode = newNode.next;
}
}
current = current.next;
}
}
Write an algorithm to reverse a linked list. The time complexity of your algorithm should be linear (O(n)). For this exercise, notice we are not asking you just to print the linked list in reverse or use another linked list to store the value in reverse order. Your program should reverse the direction of a given singly linked list. In other words, all pointers should point backward. BONUS: Solve this problem using both recursive and iterative algorithms.
Write an algorithm to find the 3rd element from the end of a linked list. Note You may be tempted to add a length property to your linked list class. The length property is not a typical property of linked list, therefore don't make any modification to the linked list class that is provided to you.
Write an algorithm to find the middle element of a linked list. Note You may be tempted to add a length property to your linked list class. The length property is not a typical property of linked list, therefore don't make any modification to the linked list class that is provided to you. Also, finding the size of the linked list using the size() function and dividing it by half will not find the correct middle of the linked list. So, don't use either of these approaches.
Write an algorithm to find whether a linked list has a cycle (i.e., whether a node in the list has its next value pointing to an earlier node in the list). For this exercise, create a linked list with the name CycleList. Be sure to insert nodes in the list so that it has a cycle. Then test your program with a cycleList function.
Implement a doubly linked list. The primary functions of the doubly linked list would be insert (First, Last, Before, After, and At), remove, and find. Write a function mainDLL, and within it create the doubly linked list DLL and add the following items to it: Aquaria, Caprica, Gemenon, Picon, Sagittaron.
- Add Tauron to the list
- Remove Picon from the list
Given the doubly linked list above, write a program that reverses the doubly linked list. How is this implementation different than reversing the singly linked list?