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:
def __init__(self, data):
self.data = data
self.next = None
class Stack:
def __init__(self):
self.top = None
def push(self, data):
new_node = Node(data)
new_node.next = self.top
self.top = new_node
print(f"Pushed: {data}")
def pop(self):
if not self.top:
print("Stack Underflow!")
return None
popped_data = self.top.data
self.top = self.top.next
print(f"Popped: {popped_data}")
return popped_data
def display(self):
current = self.top
print("Stack:", end=" ")
while current:
print(current.data, end=" -> ")
current = current.next
print("None")
# Example Run
stack = Stack()
stack.push(5)
stack.push(15)
stack.display()
stack.pop()
stack.display()Output:
Pushed: 5
Pushed: 15
Stack: 15 -> 5 -> None
Popped: 15
Stack: 5 -> NoneImplementing 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:
def __init__(self, data):
self.data = data
self.next = None
class Queue:
def __init__(self):
self.front = self.rear = None
def enqueue(self, data):
new_node = Node(data)
if not self.rear:
self.front = self.rear = new_node
else:
self.rear.next = new_node
self.rear = new_node
print(f"Enqueued: {data}")
def dequeue(self):
if not self.front:
print("Queue Underflow!")
return None
dequeued_data = self.front.data
self.front = self.front.next
if not self.front:
self.rear = None
print(f"Dequeued: {dequeued_data}")
return dequeued_data
def display(self):
current = self.front
print("Queue:", end=" ")
while current:
print(current.data, end=" -> ")
current = current.next
print("None")
# Example Run
queue = Queue()
queue.enqueue(10)
queue.enqueue(20)
queue.display()
queue.dequeue()
queue.display()Output:
Enqueued: 10
Enqueued: 20
Queue: 10 -> 20 -> None
Dequeued: 10
Queue: 20 -> NoneLinked 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)).