18-3. Doubly Linked Lists

A doubly linked list consists of nodes equipped with two pointers: one pointing to the next node and the other pointing to the previous node. These pointers are commonly referred to as the forward pointer and the backward pointer, respectively. As a result, traversal of a doubly linked list can be performed both forward and backward.

Doubly Linked List Implementation

class DoublyLinkedList:
    def __init__(self):
        self.__head = None
        self.__tail = None
        self.__size = 0

def getFirst(self):
        if self.__size == 0:
            return None
        else:
            return self.__head.element
    
    def getLast(self):
        if self.__size == 0:
            return None
        else:
            return self.__tail.element

def addFirst(self, e):
        newNode = Node(e) 
        newNode.next = self.__head
        newNode.prev = None
        if self.__head:
            self.__head.prev = newNode
        self.__head = newNode 
        if self.__tail is None:
            self.__tail = newNode
        self.__size += 1

def addLast(self, e):
        newNode = Node(e)
        newNode.prev = self.__tail
        newNode.next = None
        if self.__tail:
            self.__tail.next = newNode
        self.__tail = newNode
        if self.__head is None:
            self.__head = newNode
        self.__size += 1

def insert(self, index, e):
        if index == 0:
            self.addFirst(e) 
        elif index >= self.__size:
            self.addLast(e) 
        else: 
            current = self.__head
            for i in range(1, index):
                current = current.next

newNode = Node(e)
            newNode.next = current.next
            newNode.prev = current
            current.next.prev = newNode
            current.next = newNode
            self.__size += 1

def removeFirst(self):
        if self.__size == 0:
            return None 
        else:
            temp = self.__head 
            self.__head = self.__head.next 
            if self.__head:
                self.__head.prev = None
            self.__size -= 1
            if self.__head is None: 
                self.__tail = None 
            return temp.element

def removeLast(self):
        if self.__size == 0:
            return None 
        elif self.__size == 1: 
            temp = self.__head
            self.__head = self.__tail = None  
            self.__size = 0
            return temp.element
        else:
            temp = self.__tail
            self.__tail = self.__tail.prev
            self.__tail.next = None
            self.__size -= 1
            return temp.element

def removeAt(self, index):
        if index < 0 or index >= self.__size:
            return None 
        elif index == 0:
            return self.removeFirst() 
        elif index == self.__size - 1:
            return self.removeLast() 
        else:
            current = self.__head
            for i in range(index):
                current = current.next
            temp = current
            current.prev.next = current.next
            current.next.prev = current.prev
            self.__size -= 1
            return temp.element

def isEmpty(self):
        return self.__size == 0
    
    def getSize(self):
        return self.__size

def __str__(self):
        result = "["
        current = self.__head
        while current:
            result += str(current.element)
            current = current.next
            if current:
                result += ", " 
            else:
                result += "]" 
        return result

def clear(self):
        self.__head = self.__tail = None

def __iter__(self):
        return LinkedListIterator(self.__head)

# The modified Node class
class Node:
    def __init__(self, e):
        self.element = e
        self.next = None
        self.prev = None

class LinkedListIterator: 
    def __init__(self, head):
        self.current = head
        
    def __next__(self):
        if self.current is None:
            raise StopIteration
        else:
            element = self.current.element
            self.current = self.current.next
            return element

Last updated: April 23, 2025

Python Programming

18-3. Doubly Linked Lists