What is a Linked List?
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.
Insertion/Deletion time?
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 Implementation
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 Implementation
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.
Practice
Basic Linked List
In this problem, you will create a basic Doubly Linked List. The goal is to be able to have nodes connected all the way to 100. All you have to do is fill in the
add_front and add_back methods.Previous Session
2.2 Binary TreesCopyright © 2021 Code 4 Tomorrow. All rights reserved.
The code in this course is licensed under the MIT License.
If you would like to use content from any of our courses, you must obtain our explicit written permission and provide credit. Please contact classes@code4tomorrow.org for inquiries.