Implementing ADTs with Linked Lists
Linked lists provide a strong and effective substitute for array-based methods when implementing Abstract Data Types (ADTs), such as stacks and queues. The benefits of linked structures for dynamic data management are highlighted in the extensive discussion of this implementation strategy.
Abstract Data Types (ADTs)
An Abstract Data Type (ADT) formally represents a data structure, specifying its data types, actions, and parameters. Importantly, an ADT states the objective of each operation without prescribing its execution. This group of behaviours is used as a design tool and is frequently referred to as its public interface.
Linked Lists
A linked list is a basic type of data structure made up of a series of nodes, or elements, connected by links. Data can be placed at any available memory address in linked lists, unlike arrays, which require data to be stored in contiguous memory locations. The data element itself and a reference (or pointer) to the subsequent node in the sequence are usually the two primary components of each node in a linked list. By adding two links, doubly implementing ADTs with linked lists go beyond this and provide both forward and backwards navigation.
The ability of linked lists to dynamically resize is one of its main advantages over array-based sequences. This feature removes the requirement for expensive copy operations that arrays may require when their capacity is surpassed. Because of this, implementing ADTs with linked lists are especially appealing when it’s unclear how many things to store.
Implementing a Stack with a Linked List
In a stack, a Last-In, First-Out (LIFO) ADT, the last member inserted is dropped first. Only items from the “top” of the stack are added or removed. Because insertions and deletions can be done effectively at one end of implementing ADTs with linked lists, they are a great option for implementing stacks. The head of the linked list and the top of the stack are usually aligned for best performance. This makes it possible for all primary stack operations to run in O(1), or constant time.
The following are the main functions of a stack that uses a linked list:
- Element e is added to the top of the stack using push(e).
- pop(): Takes the element from the top of the stack and returns it.
- The element at the top is returned by top() or peek() without being removed.
- is_empty(): Checks stack contents.
- To count stack elements, use len().
A new node is made for a push operation. The list’s head is modified to point to this new node after setting its next reference to the existing head. A pop action retrieves the element from the current head node and then transfers the list’s head to the next node.
Based on material, the following conceptual Python code example shows how a stack is implemented using a singly linked list:
Example:
class Node:
_slots_ = '_element', '_next'
def _init_(self, element, next_node):
self._element = element
self._next = next_node
# LinkedStack class implementation
class LinkedStack:
"""LIFO Stack implementation using a singly linked list for storage."""
def _init_(self):
"""Create an empty stack."""
self._head = None
self._size = 0
def _len_(self):
"""Return the number of elements in the stack."""
return self._size
def is_empty(self):
"""Return True if the stack is empty."""
return self._size == 0
def push(self, e):
"""Add element e to the top of the stack."""
# Corrected: Create and link a new node, setting its next to the current head
self._head = Node(e, self._head)
self._size += 1
# O(1) amortized time
def top(self):
"""Return (but do not remove) the element at the top of the stack."""
if self.is_empty():
raise Exception("Stack is empty")
return self._head._element
def pop(self):
"""Remove and return the element from the top of the stack."""
if self.is_empty():
raise Exception("Stack is empty")
answer = self._head._element
self._head = self._head._next
self._size -= 1
return answer
# O(1) amortized time
# Example Usage
if _name_ == "_main_":
print("--- LinkedStack Demonstration ---")
my_stack = LinkedStack()
print(f"Is stack empty initially? {my_stack.is_empty()}")
my_stack.push(10)
my_stack.push(20)
print(f"\nAfter pushing 10, 20:")
print(f"Stack size: {len(my_stack)}")
print(f"Top element: {my_stack.top()}")
popped_element = my_stack.pop()
print(f"\nPopped element: {popped_element}")
print(f"Stack size after pop: {len(my_stack)}")
print(f"Top element after pop: {my_stack.top()}")
my_stack.push(30)
print(f"\nAfter pushing 30:")
print(f"Stack size: {len(my_stack)}")
print(f"Top element: {my_stack.top()}")
popped_element = my_stack.pop()
print(f"\nPopped element: {popped_element}")
popped_element = my_stack.pop()
print(f"Popped element: {popped_element}")
print(f"Stack size after all elements popped: {len(my_stack)}")
print(f"Is stack empty now? {my_stack.is_empty()}")
# Demonstrate trying to pop from an empty stack
try:
print("\nAttempting to pop from an empty stack...")
my_stack.pop()
except Exception as e:
print(f"Caught an error: {e}")
# Demonstrate trying to get top element from an empty stack
try:
print("Attempting to get top element from an empty stack...")
my_stack.top()
except Exception as e:
print(f"Caught an error: {e}")Output:
LinkedStack Demonstration
Is stack empty initially? True
After pushing 10, 20:
ERROR!
Stack size: 2
Top element: 20
Popped element: 20
Stack size after pop: 1
Top element after pop: 10
After pushing 30:
Stack size: 2
Top element: 30
Popped element: 30
Popped element: 10
Stack size after all elements popped: 0
Is stack empty now? True
Attempting to pop from an empty stack
Caught an error: Stack is empty
Attempting to get top element from an empty stack
Caught an error: Stack is emptyImplementing a Queue with a Linked List
Another Implementing ADTs with Linked Lists that stands out due to its First-In, First-Out (FIFO) principle is a queue. Elements are added to the “back” (also known as the tail) of a queue and taken out of the “front” (also known as the head). Implementing ADTs with linked lists, all operations can attain worst-case O(1) time complexity, making them ideal for queue implementations. Implementing ADTs with Linked Lists-based queues explicitly store pointers to the list’s head and tail for efficient operations at both ends.
Major operations for linked list queues:
- enqueue(e): is moved to the rear of the queue by enqueue(e).
- The first item in the queue is returned by dequeue().
- Without erasing the front element, First() returns a reference to it.
- is_empty(): Verifies whether there are any elements in the queue.
- len(): Gives back how many items are in the queue.
The tail reference is changed to the new node that is produced and connected after the current tail node when enqueue(e) is called. The new node becomes both the head and the tail if the queue was previously empty. The head reference is shifted to the following node and the element from the head node is returned for dequeue(). An important point is that the tail reference must also be set to None for consistency if the queue becomes empty after dequeuing.
Below is an example of conceptual Python code for a queue that uses a single linked list:
Example:
class Node:
_slots_ = '_element', '_next'
def _init_(self, element, next_node):
"""
Initializes a new Node.
Args:
element: The data element to be stored in the node.
next_node: A reference to the next node in the sequence (or None if it's the last node).
"""
self._element = element
self._next = next_node
# LinkedQueue class implementation
# This class implements a FIFO (First-In, First-Out) queue using a singly linked list.
class LinkedQueue:
"""FIFO Queue implementation using a singly linked list for storage."""
def __init__(self):
"""
Create a new empty Queue.
Initializes the head, tail, and size of the queue.
"""
self._head = None
self._tail = None
self._size = 0
def __len__(self):
"""
Return the number of items in the queue.
This operation is O(1) time complexity.
"""
return self._size
def is_empty(self):
"""
Return True if the queue is empty, False otherwise.
This operation is O(1) time complexity.
"""
return self._size == 0
def first(self):
"""
Return (but do not remove) the element at the front of the queue.
Raises an Exception if the queue is empty.
This operation is O(1) time complexity.
"""
if self.is_empty():
raise Exception("Queue is empty")
return self._head._element
def dequeue(self):
"""
Remove and return the first element of the queue (i.e., FIFO).
Raises an Exception if the queue is empty.
This operation is O(1) amortized time complexity.
"""
if self.is_empty():
raise Exception("Queue is empty")
answer = self._head._element
self._head = self._head._next
self._size -= 1
if self.is_empty():
self._tail = None
def enqueue(self, e):
"""
Add an element to the back of queue.
This operation is O(1) amortized time complexity.
"""
# Create a new Node. IMPORTANT: Node is a top-level class, so we call Node(e, None)
newest = Node(e, None)
if self.is_empty():
self._head = newest
else:
self._tail._next = newest
self._tail = newest
self._size += 1
# Example Usage
if __name__ == "__main__":
print("--- LinkedQueue Demonstration ---")
my_queue = LinkedQueue()
print(f"Is queue empty initially? {my_queue.is_empty()}")
my_queue.enqueue(100)
my_queue.enqueue(200)
print(f"\nAfter enqueuing 100, 200:")
print(f"Queue size: {len(my_queue)}")
print(f"Front element: {my_queue.first()}")
dequeued_element = my_queue.dequeue()
print(f"\nDequeued element: {dequeued_element}")
print(f"Queue size after dequeue: {len(my_queue)}")
print(f"Front element after dequeue: {my_queue.first()}")
my_queue.enqueue(300)
print(f"\nAfter enqueuing 300:")
print(f"Queue size: {len(my_queue)}")
print(f"Front element: {my_queue.first()}")
dequeued_element = my_queue.dequeue()
print(f"\nDequeued element: {dequeued_element}")
dequeued_element = my_queue.dequeue()
print(f"Dequeued element: {dequeued_element}")
print(f"Queue size after all elements dequeued: {len(my_queue)}")
print(f"Is queue empty now? {my_queue.is_empty()}")
# Demonstrate trying to dequeue from an empty queue
try:
print("\nAttempting to dequeue from an empty queue...")
my_queue.dequeue()
except Exception as e:
print(f"Caught an error: {e}")
try:
print("Attempting to get first element from an empty queue...")
my_queue.first()
except Exception as e:
print(f"Caught an error: {e}")Output:
LinkedQueue Demonstration
Is queue empty initially? True
After enqueuing 100, 200:
Queue size: 2
Front element: 100
Dequeued element: 100
Queue size after dequeue: 1
Front element after dequeue: 200
After enqueuing 300:
Queue size: 2
Front element: 200
ERROR!
Dequeued element: 200
Dequeued element: 300
Queue size after all elements dequeued: 0
Is queue empty now? True
Attempting to dequeue from an empty queue...
Caught an error: Queue is empty
Attempting to get first element from an empty queue...
Caught an error: Queue is emptyLinked lists are quick and flexible and are used for both stack and queue operations. If members need to be moved or the array needs to be dynamically increased, array-based solutions might perform worse (amortised O(1) for resizing, or O(n) worst-case time for Python list operations like pop(0)).