Implementing Linked-Based Data Structures

Gregory M. Kapfhammer

March 10, 2025

What is a linked list?

• Stores a sequential collection of elements
• Uses individual nodes to store data values
• Each node has a reference to the next node
• The first node is called the head and the last is the tail
• Enables list traversal in a “forward” direction

class ListNode:
    def __init__(self, data, link = None):
        self.data = data
        self.link = link

Implementing a LinkedList

class LinkedList:
    def __init__(self):
        self._head = None

    def addfirst(self, item):
        self._head = ListNode(item, self._head)

    def removefirst(self):
        item = self._head.data
        self._head = self._head.link
        return item

• Using self to reference the current instance of LinkedList
• A LinkedList contains an instance of ListNode in _head
• addfirst creates a new ListNode and updates _head
• removefirst updates _head and returns the data

LinkedList Structure Visualization

graph LR
    Head["_head"] --> Node1["Node 1<br>data: 42"]
    Node1 --> Node2["Node 2<br>data: 17"]
    Node2 --> Node3["Node 3<br>data: 99"]
    Node3 --> Null["None"]
    
    classDef nodeStyle fill:#f9f9f9,stroke:#333,stroke-width:1px
    classDef nullStyle fill:#f0f0f0,stroke:#999,stroke-dasharray: 5 5
    
    class Node1,Node2,Node3 nodeStyle
    class Null nodeStyle
    class Head nodeStyle

• Each box represents a ListNode object that contains:
  • data that stores the value
  • link that points to the next ListNode
• Arrows indicate link references to the next node
• The _head attribute points to the first node in the list
• The ListNode storing None marks the end of the linked list
• Adding or removing nodes changes the link references!

Making a Queue with a LinkedList

class LinkedList:
    def __init__(self):
        self._head = None

    def addfirst(self, item):
        self._head = ListNode(item, self._head)

    def addlast(self, item):
        if self._head is None:
            self.addfirst(item)
        else:
            currentnode = self._head
            while currentnode.link is not None:
                currentnode = currentnode.link
            currentnode.link = ListNode(item)

    def removefirst(self):
        item = self._head.data
        self._head = self._head.link
        return item

    def removelast(self):
        if self._head.link is None:
            return self.removefirst()
        else:
            currentnode = self._head
            while currentnode.link.link is not None:
                currentnode = currentnode.link
            item = currentnode.link.data
            currentnode.link = None
            return item

Using the LinkedList

LL = LinkedList()
LL.addfirst(3)
LL.addfirst(5)
print(LL.removefirst() == 5)
LL.addlast(9)
LL.addlast(13)
print(LL.removefirst() == 3)
print(LL.removefirst() == 9)
print(LL.removelast() == 13)

True
True
True
True

• This LinkedList can be used to build a Queue
• However, two of these methods have while loops!
• This means it is not always better than the ListQueue

Explore use of the LinkedList

• Key Task: After finding definitions of ListNode and LinkedList, draw a picture to show their relationship! Can you explain the True outputs?

Concerns about this LinkedList?

• addlast
• removelast

def addlast(self, item):
    if self._head is None:
        self.addfirst(item)
    else:
        currentnode = self._head
        while currentnode.link is not None:
            currentnode = currentnode.link
        currentnode.link = ListNode(item)

• while currentnode.link is not None is not efficient!
• Access to the final node requires traversing the entire list
• This is a \(O(n)\) (or linear-time) operation!

def removelast(self):
    if self._head.link is None:
        return self.removefirst()
    else:
        currentnode = self._head
        while currentnode.link.link is not None:
            currentnode = currentnode.link
        item = currentnode.link.data
        currentnode.link = None
        return item

• while currentnode.link.link is not None efficient?
• removelast traverses all nodes to find second-to-last one!
• This is a \(O(n)\) (or linear-time) operation!

Recap Stack, Queue, and Deque

• Abstract data types versus concrete data structures
  • Stack: LIFO discipline with push, pop, peek
  • Queue: FIFO discipline with enqueue, dequeue, peek
  • Deque: addfirst, addlast, removefirst, removelast
• Implementations of the Stack, Queue, and Deque
  • Stack: ListStack, InefficientListStack, RobustStack
  • Queue: ListQueueSimple, … , ListQueue
  • Deque: ListDeque
• We need faster functions while preserving features!

Let’s implement these structures using a LinkedList!

• Build a Queue and/or Deque with a LinkedList
• Identify performance limitations and improve them
• Revise the LinkedList movement in both directions
• Explore the trade-offs between time and space overhead

Better Queue with a LinkedList?

class LinkedListTrial:
    def __init__(self):
        self._head = None
        self._tail = None

    def addfirst(self, item):
        self._head = ListNode(item, self._head)
        if self._tail is None: self._tail = self._head

    def addlast(self, item):
        if self._head is None:
            self.addfirst(item)
        else:
            self._tail.link = ListNode(item)
            self._tail = self._tail.link

    def removefirst(self):
        item = self._head.data
        self._head = self._head.link
        if self._head is None: self._tail = None
        return item

    def removelast(self):
        if self._head is self._tail:
            return self.removefirst()
        else:
            currentnode = self._head
            while currentnode.link is not self._tail:
                currentnode = currentnode.link
            item = self._tail.data
            self._tail = currentnode
            self._tail.link = None
            return item

Using the LinkedListTrial

LL = LinkedListTrial()
LL.addfirst(3)
LL.addfirst(5)
print(LL.removefirst() == 5)
LL.addlast(9)
LL.addlast(13)
print(LL.removefirst() == 3)
print(LL.removefirst() == 9)
print(LL.removelast() == 13)

True
True
True
True

• Wow, this LinkedList can be used to build a Queue
• However, one of these methods still has a while loop!
• This means it is not always better than the ListQueue

LinkedListTrial concerns?

• addlast
• removelast

def addlast(self, item):
    if self._head is None:
        self.addfirst(item)
    else:
        self._tail.link = ListNode(item)
        self._tail = self._tail.link

• There is no longer a while loop in addlast
• When there is no data, addfirst is called
• Otherwise, self._tail is updated and new node is added
• Adding a node to the end of the list is now \(O(1)\)!

def removelast(self):
    if self._head is self._tail:
        return self.removefirst()
    else:
        currentnode = self._head
        while currentnode.link is not self._tail:
            currentnode = currentnode.link
        item = self._tail.data
        self._tail = currentnode
        self._tail.link = None
        return item

• while currentnode.link is not self._tail efficient?
• removelast still traverses nodes to perform a removal!

Tracking the size of a LinkedList

class LinkedListPrime:
    def __init__(self):
        self._head = None
        self._tail = None
        self._length = 0

    def addfirst(self, item):
        self._head = ListNode(item, self._head)
        if self._tail is None: self._tail = self._head
        self._length += 1

    def addlast(self, item):
        if self._head is None:
            self.addfirst(item)
        else:
            self._tail.link = ListNode(item)
            self._tail = self._tail.link
            self._length += 1

    def removefirst(self):
        item = self._head.data
        self._head = self._head.link
        if self._head is None: self._tail = None
        self._length -= 1
        return item

    def removelast(self):
        if self._head is self._tail:
            return self.removefirst()
        else:
            currentnode = self._head
            while currentnode.link is not self._tail:
                currentnode = currentnode.link
            item = self._tail.data
            self._tail = currentnode
            self._tail.link = None
            self._length -= 1
            return item

    def __len__(self):
        return self._length

Constructor for the LinkedListPrime

class LinkedListPrime:
    def __init__(self):
        self._head = None
        self._tail = None
        self._length = 0

• As with other classes, the constructor is called __init__
• The self variable enables access to the instance attributes
• The class continues to use the _head and _tail attributes
• Add the _length attribute to make it easy to track size
• Start the size of a LinkedListPrime instance at zero
• Question: which methods have to update the _length?

How do methods influence the size?

__init__

• Initializes the size to zero
• self._length = 0 is a \(O(1)\) operation

addfirst and addlast

• Both methods increment the size by one
• self._length += 1 is a \(O(1)\) operation

removefirst and removelast

• Both methods decrement the size by one
• self._length -= 1 is a \(O(1)\) operation

Using improved LinkedList

LL = LinkedListPrime()
LL.addfirst(3)
LL.addfirst(5)
print(LL.removefirst() == 5)
LL.addlast(9)
LL.addlast(13)
print(LL.removefirst() == 3)
print(LL.removefirst() == 9)
print(LL.removelast() == 13)
print(len(LL) == 0)

True
True
True
True
True

• LinkedListPrime has features equivalent to LinkedListNew
• Represents an improved building block for a Queue-like structure

LinkedQueue with a LinkedList

class LinkedQueue:
    def __init__(self):
        self._L = LinkedListPrime()

    def enqueue(self, item):
        self._L.addlast(item)

    def dequeue(self):
        return self._L.removefirst()

    def peek(self):
        item = self._L.removefirst()
        self._L.addfirst(item)
        return item

    def display(self):
        current = self._L._head
        while current is not None:
            print(current.data, end=" ")
            current = current.link

    def __len__(self):
        return len(self._L)

    def isempty(self):
        return len(self) == 0

Using the LinkedQueue

def manipulate_queue():
    queue = LinkedQueue()
    queue.enqueue('umbrella')
    queue.enqueue('backpack')
    queue.enqueue('sandals')
    print("Queue contents after enqueue operations:", end=" ")
    queue.display()
    queue.dequeue()
    print("\nQueue contents after dequeue operation:", end=" ")
    queue.display()

manipulate_queue()

Queue contents after enqueue operations: umbrella backpack sandals 
Queue contents after dequeue operation: backpack sandals 

• LinkedQueue is functionally equivalent to the ListQueue
• The LinkedQueue uses display to reveal the contents

Reviewing efficient adding operations

def addfirst(self, item):
    self._head = ListNode(item, self._head)
    if self._tail is None: self._tail = self._head
    self._length += 1

def addlast(self, item):
    if self._head is None:
        self.addfirst(item)
    else:
        self._tail.link = ListNode(item)
        self._tail = self._tail.link
        self._length += 1

• Neither of these methods have a loop in them
• Assignment statements and conditional logic are \(O(1)\)
• Importantly, all of the method calls are also \(O(1)\)

Wait, inefficient data removal!

def removefirst(self):
    item = self._head.data
    self._head = self._head.link
    if self._head is None: self._tail = None
    self._length -= 1
    return item

def removelast(self):
    if self._head is self._tail:
        return self.removefirst()
    else:
        currentnode = self._head
        while currentnode.link is not self._tail:
            currentnode = currentnode.link
        item = self._tail.data
        self._tail = currentnode
        self._tail.link = None
        self._length -= 1
        return item

Okay, let’s explore the inefficiency in the removelast method!

def removelast(self):
    if self._head is self._tail:
        return self.removefirst()
    else:
        currentnode = self._head
        while currentnode.link is not self._tail:
            currentnode = currentnode.link
        item = self._tail.data
        self._tail = currentnode
        self._tail.link = None
        self._length -= 1
        return item

• The while loop in removelast is a \(O(n)\) operation
• Looping is needed to find the second-to-last node

Improve performance of a Queue using a LinkedList?

• Discuss performance problem with members of your table
• Create a technical diagram of a LinkedList and its nodes
• Step through the code and move through LinkedList
• Identify the performance problem and propose solution(s)

To achieve performance improvements, we need a doubly linked list!

• Stores a sequential collection of elements
• Uses individual nodes to store data values
• Each node has a reference to the next and previous node
• Enable list traversal in forward and backward directions

Creating a new ListNode

class ListNode:
    def __init__(self, data, prev = None, link = None):
        self.data = data
        self.prev = prev
        self.link = link
        if prev is not None:
            self.prev.link = self
        if link is not None:
            self.link.prev = self

• self.data stores the data value inside of the ListNode
• self.prev stores a reference to the previous ListNode
• self.link stores a reference to the next ListNode
• Key invariant for the ListNode: for any two nodes a and b, it must be true that b == a.link if and only if a = b.prev

Attempting the DoublyLinkedList

class DoublyLinkedList:
    def __init__(self):
        self._head = None
        self._tail = None
        self._length = 0

    def addfirst(self, item):
        if len(self) == 0:
            self._head = self._tail = ListNode(item, None, None)
        else:
            newnode = ListNode(item, None, self._head)
            self._head.prev = newnode
            self._head = newnode
        self._length += 1

    def addlast(self, item):
        if len(self) == 0:
            self._head = self._tail = ListNode(item, None, None)
        else:
            newnode = ListNode(item, self._tail, None)
            self._tail.link = newnode
            self._tail = newnode
        self._length += 1

    def __len__(self):
        return self._length

Wait, code redundancy suggests an opportunity to refactor the source code in addfirst and addlast!

def _addbetween(self, item, before, after):
    node = ListNode(item, before, after)
    if after is self._head:
        self._head = node
    if before is self._tail:
        self._tail = node
    self._length += 1

• Define an “internal method” called _addbetween
• The addfirst and addlast methods call _addbetween
• Importantly, this method is an efficient \(O(1)\) operation!

Refactoring the DoublyLinkedList

class DoublyLinkedList:
    def __init__(self):
        self._head = None
        self._tail = None
        self._length = 0

    def __len__(self):
        return self._length

    def _addbetween(self, item, before, after):
        node = ListNode(item, before, after)
        if after is self._head:
            self._head = node
        if before is self._tail:
            self._tail = node
        self._length += 1

    def addfirst(self, item):
        self._addbetween(item, None, self._head)

    def addlast(self, item):
        self._addbetween(item, self._tail, None)

    def _remove(self, node):
        before, after = node.prev, node.link
        if node is self._head:
            self._head = after
        else:
            before.link = after
        if node is self._tail:
            self._tail = before
        else:
            after.prev = before
        self._length -= 1
        return node.data

    def removefirst(self):
        return self._remove(self._head)

    def removelast(self):
        return self._remove(self._tail)

    def display(self):
        current = self._head
        while current is not None:
            print(current.data)
            current = current.next

Refactored DoublyLinkedList

• _addbetween method:
  • Adds a new node between two existing nodes
  • Uses the _head or _tail node as needed
  • Both addfirst and addlast call this method
• _remove method:
  • Removes a node between two existing nodes
  • Uses the prev or link node as needed
  • Both removefirst and removelast call this method
• Wow, both of these methods are efficient \(O(1)\) operations!

Efficiency of the display method?

def display(self):
    current = self._head
    while current is not None:
        print(current.data)
        current = current.next

• The display method is a \(O(n)\) operation
• The while loop traverses all nodes in the list
• The time complexity is proportional to list’s length
• This makes sense since we must visit all nodes!

Insight: Unless we only need to display a subset of the list, the \(O(n)\) time complexity is the best that we can achieve for display!

Using the DoublyLinkedList

def manipulate_doubly_linked_list():
    DLL = DoublyLinkedList()
    print(len(DLL))
    DLL.addfirst(3)
    DLL.addfirst(5)
    print(DLL.removefirst() == 5)
    DLL.addlast(9)
    DLL.addlast(13)
    print(DLL.removefirst() == 3)
    print(DLL.removefirst() == 9)
    print(DLL.removefirst() == 13)
    print(len(DLL))

manipulate_doubly_linked_list()

0
True
True
True
True
0

How do we join together structures like List or DoublyLinkedList?

A = [1,2,3]
B = [4,5,6]
C = A + B
print(A)
print(B)
print(C)

[1, 2, 3]
[4, 5, 6]
[1, 2, 3, 4, 5, 6]

• The line C = A + B concatenates the two lists together
• Python’s implementation of + creates a new list
• Takes time proportional length of C without modifying A or B

If modification of DoublyLinkedList permitted, efficient concatenation!

def __iadd__(self, other):
    if other._head is not None:
        if self._head is None:
            self._head = other._head
        else:
            self._tail.link = other._head
            other._head.prev = self._tail
        self._tail = other._tail
        self._length = self._length + other._length
        other.__init__()
    return self

• No need to traverse the entire list in __iadd__!
• The internal __iadd__ method is called when += is used
• The other DoublyLinkedList is concatenated to self

Concatenation for DoublyLinkedList

L = DoublyLinkedList( **Key Insight**:)
[L.addlast(i) for i in range(11)]
B = DoublyLinkedList()
[B.addlast(i+11) for i in range(10)]

L += B

n = L._head
while n is not None:
    print(n.data, end = ' ')
    n = n.link

• The DoublyLinkedList L is concatenated with B
• Using += calls the __iadd__ method in DoublyLinkedList
• List B is “drained” of values when it is the other parameter
• Is this an efficient way to perform concatenation? Well …

How can we now implement a Deque with a DoublyLinkedList?

• A Deque, or a double-ended queue, will contain an instance of the DoublyLinkedList as was done previously
• Enables efficient addition and removal at both Deque ends
• Hooray, all methods in this Deque are \(O(1)\) operations!

Insights about the design and implementation of data structures

Design Considerations

• One structure can be used to build another
• A structure’s design can influence its performance
• Fundamental limitations arise with certain designs

Implementation Trade-offs

• Refactoring can improve a structure’s implementation
• Assumptions about modification influence performance
• Overloading operator built-ins enhances convenience