Linked List

A linked list is a linear data structure in which elements (nodes) are connected using pointers.

Always read the question as they can often hint or guide you on what you have to do.
Questions may also ask you to come up with new functions.
Hence it is crucial to understand how the code works and be able to adapt and modify it.

Below are key operations and examples:

1. Structure of a Node

A Node contains two parts:
- Data: Stores the actual data of the node.
- Pointer: Stores the reference to the next node.

class Node:
    def __init__(self, data, pointer=None):
        self.__data = data
        self.__pointer = pointer

    def getPointer(self):
        return self.__pointer

    def setPointer(self, pointer):
        self.__pointer = pointer

    def getData(self):
        return self.__data

    def setData(self, data):
        self.__data = data

2. Operations in a Linked List

The LinkedList class provides methods to manipulate and traverse the list.
Below are examples of operations like inserting, deleting, and displaying elements.

a) Inserting at the Head

Adds a new node at the beginning of the list.

class LinkedList:
    def insertHead(self, data):
        newnode = Node(data)
        if self.isEmpty():
            self.__head = newnode
        else:
            newnode.setPointer(self.__head)
            self.__head = newnode

b) Inserting at the Tail

Adds a new node at the end of the list.

def insertTail(self, data):
    newnode = Node(data)
    if self.isEmpty():
        self.__head = newnode
    else:
        curr = self.__head
        while curr.getPointer() != None:
            curr = curr.getPointer()
        curr.setPointer(newnode)

c) Deleting the Head

Removes the first node in the list.

def deleteHead(self):
    if self.isEmpty():
        print(f'Nothing to delete')
    else:
        self.__head = self.__head.getPointer()

d) Calculating the Length

Counts the number of nodes in the list.

def length(self):
    count = 0
    curr = self.__head
    while curr != None:
        count += 1
        curr = curr.getPointer()
    return count

e) Displaying the List

Traverses and prints all nodes in the list.

def display(self):
    if self.isEmpty():
        print(f'List is Empty')
    else:
        curr = self.__head
        while curr != None:
            print(f'{curr.getData()}')
            curr = curr.getPointer()

3. Example Usage

Below is an example demonstrating how to use the LinkedList class:

# Main
linked_list = LinkedList()

# Insert nodes
linked_list.insertHead(10)
linked_list.insertTail(20)
linked_list.insertTail(30)

# Display list
linked_list.display()

# Delete head
linked_list.deleteHead()
linked_list.display()

# Length of list
print(f'Length: {linked_list.length()}')

---------------------------------------

10
20
30
20
30
Length: 2

Navigation