A LinkedList is another type of data structure. A LinkedList consists of a number of nodes, which contain a value, a pointer that points to the next node in the list, and a pointer that points to the previous node in the list. Note that, if the LinkedList’s nodes only have pointers to the next item, the linked list is a “singly linked list,” while linked lists whose nodes have pointers to the next and previous nodes are called “doubly linked lists.”
Example:
In this way, a linked list is pretty similar to a regular list. However, the main difference is the insertion/deletion time taken for these data structures. Data structures are used to store data and algorithms are used to solve problems using the data. In this way, a linked list is pretty similar to a regular list. However, the main difference is the insertion/deletion time taken for these data structures.
For normal lists, it takes O(n) time to remove or insert an item from a list. This is because it requires iterating through the items until it has reached the desired index before removing or inserting an item. Then, it has to shift any elements that were in a greater index either to the right or to the left (depending on whether it was insertion or deletion).
In a linked list, however, it can take as little as O(1) time (depending on the location of the insertion or deletion)
Java already has an implementation of the linked list in the java.util package.
Here’s an example showing its efficacy in insertion and deletion.
import java.util.ArrayList;
import java.util.LinkedList;
public class LinkedLists {
public static void main(String[] args) {
int TEST_SIZE = 200000;
LinkedList<Integer> myDouble = new LinkedList<>();
long start = System.nanoTime();
for (int i = 0; i < TEST_SIZE; i++) {
myDouble.add(0, i);
}
long end = System.nanoTime();
System.out.println("Took " + (double) (end - start) / 1e9 + " seconds to add front doubly");
ArrayList<Integer> myRegular = new ArrayList<>();
start = System.nanoTime();
for (int i = 0; i < TEST_SIZE; i++) {
myRegular.add(0, i);
}
end = System.nanoTime();
System.out.println("Took " + (double) (end - start) / 1e9 + " seconds to add front regularly");
start = System.nanoTime();
for (int i = 0; i < TEST_SIZE - 1; i++) {
myDouble.remove(0);
}
end = System.nanoTime();
System.out.println("Took " + (double) (end - start) / 1e9 + " seconds to remove front doubly");
start = System.nanoTime();
for (int i = 0; i < TEST_SIZE - 1; i++) {
myRegular.remove(0);
}
end = System.nanoTime();
System.out.println("Took " + (double) (end - start) / 1e9 + " seconds to remove front regularly");
// compare results
System.out.println(myDouble);
System.out.println(myRegular);
}
}
Python doesn’t have a default implementation of the linked list. So, here is an example implementation of the doubly linked list that has most of the methods and attributes of the java version. At the bottom of the file, there are tests that showcase the insertion and deletion time of doubly linked lists vs regular python lists.
from datetime import datetime as d
class Node:
def __init__(self, value, prev=None, next=None) -> None:
self.value = value
self.prev = prev
self.next = next
class DoublyLinkedList:
def __init__(self) -> None:
self.head = Node(None)
self.head.next = Node(None, self.head)
self.tail = self.head.next
self.size = 0
def add_current(self, value, current) -> bool:
"""
Helper method
O(1) operation
Arguments:
@param value - the value to insert
@param current - the node to insert the value in front of
@returns bool - True on success
"""
if current.next is None:
current.next = Node(value, current)
else:
current.next = Node(value, current, current.next)
if current.next.next:
current.next.next.prev = current.next
self.size += 1
return True
def add_front(self, value) -> bool:
"""
O(1) operation
"""
return self.add_current(value, self.head)
def add_back(self, value) -> bool:
"""
O(1) operation
"""
return self.add_current(value, self.tail.prev)
def add(self, value, idx) -> bool:
"""
O(N) operation since it has to iterate to idx
"""
if idx > self.size:
return False
current = self.head
for i in range(idx):
current = current.next
self.add_current(value, current)
def set(self, value, idx) -> bool:
"""
O(N) operation since it has to iterate to idx
"""
if idx >= self.size:
return False
current = self.head.next
for i in range(idx):
current = current.next
current.value = value
return True
def set_front(self, value) -> bool:
"""
O(1) operation
"""
if self.size == 0:
return False
self.head.next.value = value
return True
def set_back(self, value) -> bool:
"""
O(1) operation
"""
if self.size == 0:
return False
self.tail.prev.value = value
return True
def remove_current(self, current) -> bool:
"""
Helper method (O(1) operation)
Arguments:
@param current - the node to be removed
@returns bool - True on success
"""
current.prev.next = current.next
if current.prev.next:
current.prev.next.prev = current.prev
self.size -= 1
return True
def remove_value(self, value) -> bool:
"""
Attempts to remove the first occurrence of value from the list.
O(N) operation since it has to iterate through the list to find the value
@returns bool - True on success (value found and removed),
False on failure to find the value
"""
current = self.head.next
# advance the cursor until either we've reached the end
# of the list or we've reached the value
while current != self.tail and current.value != value:
current = current.next
# found the item, time to remove
if current != self.tail and current.value == value:
self.remove_current(current)
return True
# didn't find the item
return False
def remove_front(self) -> bool:
if self.size == 0:
return True
return self.remove_current(self.head.next)
def remove_back(self) -> bool:
if self.size == 0:
return True
return self.remove_current(self.tail.prev)
def remove_idx(self, idx) -> bool:
"""
O(N) operation since it has to iterate to idx
"""
if idx >= self.size:
return False
current = self.head.next
for i in range(idx):
current = current.next
return self.remove_current(current)
def clear(self) -> bool:
"""
O(1) operation
"""
self.head.next = self.tail
self.tail.prev = self.head
self.size = 0
def __str__(self) -> str:
ret = "["
current = self.head.next
while current.next is not None:
ret += str(current.value)
current = current.next
if current.next is not None:
ret += ", "
ret += "]"
return ret
def print_from_front(self) -> None:
print(self)
def print_from_back(self) -> None:
current = self.tail.prev
print("[", end="")
while current.prev is not None:
print(current.value, end="")
current = current.prev
if current.prev is not None:
print(", ", end="")
print("]")
my_double = DoublyLinkedList()
my_regular = []
TEST_SIZE = 100000
start = d.now()
for i in range(TEST_SIZE):
my_regular.insert(0, i)
end = d.now()
print(f"it took {(end-start).total_seconds()} seconds to do that regularly")
start = d.now()
for i in range(TEST_SIZE):
my_double.add_front(i)
end = d.now()
print(f"it took {(end-start).total_seconds()} seconds to do that doubly")
start = d.now()
for i in range(TEST_SIZE - 1):
my_regular.pop(0)
end = d.now()
print(f"it took {(end-start).total_seconds()} seconds to do that regularly")
start = d.now()
for i in range(TEST_SIZE - 1):
my_double.remove_front()
end = d.now()
print(f"it took {(end-start).total_seconds()} seconds to do that doubly")
print(my_regular)
print(my_double)
View code on GitHub.