Linked Structures

• Arrays are basic sequence containe with easy and direct access to the individual elements however they are limited in their functionality

• Python lists implemented using an array structure, which extends arrays' functionality by providing largers sets of operations.

• Fixed array size, insertion and deletion times, are some problems of Arrays, and Python lists.

• Linked list data structure can be used to store a collection in linear order.
• Several variaties of linked liss are singly linked lists, and doubly linked lists.

Introduction

Let's create a basic class containing sigle data field:

This is will give us just the containers that we can store data into.

Since we did not define a method to show the value stored, we cannot see the value. However the values we passed to each variable is stored.

Now to make it a linked list, we have to establish a connection. To achieve this we can add another data field called next into our constructor.

After modifying the ListNode class and creating nodes for testing we need to use next field to assign it to next node to establish a connection.

• Linked Structure contains nodes with data inside them and at least one reference or link to another.
• Last node is commonly called the tail node, which is indicated by a null link reference.
• The first node in the list is referenced by an external variable as it provides an entry point into the linked list, this variable called head reference.

The Singly Linked List

• Linked Lists with single connection allowed.

1. Traversing the Nodes

Connecting all the nodes together in large list of nodes is impractical with as we did in the early example. Instead we will use a temporary external reference to traverse through the list, moving the reference along as we access the individual nodes.

def traversal(head):
    curNode = head
    while curNode is not None:
        print(curNode.data)
        curNode = curNode.next

A complete list traversal requires O(n) time.

2. Searching for a Node

Linear search operation can be performed on a linked list, using the same principle we did with traversal.

def unorderedSearch(head, target):
    curNode = head
    while curNode is not None and curNode.data != target:
        curNode = curNode.next
    return curNode is not None

Search operation requires O(n) in the worst case

3. Prepending Nodes

Prepending a node can be done in constant time since no traversal is required, because we simply maintain the head reference. One simple example of prepending:

newNode = ListNode(item)
newNode.next = head
head = newNode

When we add a new value here are the steps followed:

• Create a new node to store the new value
• Set it's next field to point to the node currently at the front of the list
• Adjust head to point to the new node since it's now the first node

Careful of the order of the new links, because if we link the new node into the list before modifying the head reference we lose our external reference, which results losing the list itself.

4. Removing Nodes

Removing nodes or unlinking them will simply extract them from the linked list structure. The steps:

• Find the node containing value and position the external reference pointing to it.
• Unlink from the list by setting node's link field to None
• Access the node's successor by assigning extra next link to node.

Removing the first node is a special case, because head references the node.

# Given the head reference, remove a target from a linked list.
predNode = None
curNode = head

while curNode is not None and curNode.data != target:
    predNode = curNode
    curNode = curNode.next

if curNode is not None:
    if curNode is head:
        head = curNode.next
    else:
        predNode.next = curNode.next

More ways to Build a Linked List

Sometimes we need extra flexibility in our linked list than having only basic container with linear order, that's why now we'll see some features.

Using a Tail Reference

Using a both head and tail might save us some time, when we need to append nodes to end of the linked list.

Adding Node using Tail Reference:

# Given the head and tail pointers, adds an item to a linked list.
newNode = ListNode(item)
if head is None:
    head = newNode
else:
    tail.next = newNode

tail = newNode

Removing Node using Tail Reference:

# Given the head and tail references, removes a target from a linked list. 
predNode = None
curNode = head

while curNode is not None and curNode.data != target:
    predNode = curNode
    curNode = curNode.next

if curNode is not None:
    if curNode is head:
        head = curNode.next
    else:
        predNode.next = curNode.next

    if curNode is tail:
        tail = predNode

The Sorted Linked List

We can store elements in linked list as sorted.

Linear Search

Linear search in sorted linked list will be faster since we add extra condition to terminates the loop when we reach the bigger number.

def sortedSearch(head, target):
    curNode = head
    while curNode is not None and curNode.data < target:
        if curNode.data == target:
            return True
        else:
            curNode = node.next
    return False

Inserting Nodes

Adding a node to sorted linked list a little bit more trickier, since we have to find the spot to put our Node into sorted list.

# Given the head pointer, insert a value into a sorted linked list.
@ToDo: # Review and fix the function 
def insert2sorted(head):
    # Find the insertion point for the new value.
    predNode = None
    curNode = head

    while curNode is not None and value > curNode.data:
        predNode = curNode
        curNode = curNode.next

    # Create the new node for the new value.
    newNode = ListNode(value)
    newNode.next = curNode
    # Link the new node into the list.
    if curNode is head:
        head = newNode
    else:
        predNode.next = newNode

Traversing and Deleting

It's pretty much the same for sorted linked lists as it was in normal linked lists.