CS131: Linked List

A linked list is a linear data structure where each element keeps a pointer to track elements in linear order. If the foirst element of the list is accessible, it is possible to access any element of the list. Each element of the list is called to a node which stores data and reference to next node of the list.
We use a special node marked as head to reference the first node of the list.
In a singly linked list each node stores data and keeps reference to the next node. First node is referenced by head and last node does not have a next node reference.

[head|o]--->[data1|o]--->[data2|o]--->[data3|o]--->%

Fig: A singly linked list
I a doubly linked list each node stores data and keeps reference to the previous node and the next node. First node does not have a previous node reference and last node does not have a next node reference.

[head|o]--->[o|data1|o]--->[o|data2|o]--->[o|data3|o]--->%
             |     ^        |    ^         |
       %<----+     +--------+    +---------+

Fig: A doubly linked list
A circular list is similar to singly where each nor keeps reference to the next node adn the last node references the first node as its next node reference. Head points to the first item which can be any item in the list because of the circular nature of the list.

[head|o]--->[data1|o]--->[data2|o]--->[data3|o]---+
              ^                                   |
              |                                   |
              +-------------[o|data4]<------------+

Fig: A circular linked list

Representing linked list

class SNode
{  
    object data;
    SNode next;
};

class SNode
{  
    object data;
    SNode next, prev;
};

class SList
{      
    SNode head;
    int itemCount;
};

class DList
{      
    DNode head;
    int itemCount;
};

Insert Operation

We want to insert a node at the front of the list

void insert(SList list, object data)
{
    SNode node = new SNode();
    node.data = data;
    node.next = list.head;
    list.head = node;
}

Quiz: Hou would ypu modify the list or the insert method to insert an item at the end of the list in O(1) time.
Quiz: How would you implement a stack using a linked list
Problem: Implement a doubly linked list
Problem: Implement a circular list

Find operation

Given a data value we need to find the node that stores that data. We the head item to get first item in the list and follow the next reference to find the item with given data or we reach the end of the list.

SNode find(SList list, object data)
{
    SNode cur = list.head;
    while(cur != null && !cur.data.equals(data))
    {
        cur = cur.next;
    }
    return cur;
}

Since there is no way to find a middle item of the list directly, find takes O(n) time even for a sorted list.

Delete operation

Let us consider the following list:

[head|o]--->[  5 |o]--->[  9 |o]--->[  6 |o]--->[ 13 |o]--->%

If we want to delete the element with data 9 the list will be like this after deletion:

[head|o]--->[  5 |o]--->[  6 |o]--->[ 13 |o]--->%

One way to do this is by finding previous element in the list and then delete the item and copying the next reference from the node we are deleting. This will take O(n) time. If the node is not last node in the list we can do it in O(1) time by copying the data and next reference from the next node and then deleting the next node.

[head|o]--->[  5 |o]--->[  6 |o]-X->[  6 |o]--->[ 13 |o]--->%
                            |       delete        ^
                            +---------------------+

void delete(SList list, SNode node)
{
    if(node.next != null)
    {
        node.data=node.next.data;
        node.next = node.next.next;
    }
    else
    {
        SNode cur = list.head;

        if(cur == node)
            list.head=null;

        while(cur.next != node)
        {
            cur = cur.next;
        }
        cur.next = node.next;                
    }
}

Most of the time the delete operation will complete in constant time. But for the last node it'll take O(n) time. To avoid the situation we can use a specual node called sentinel node to mark the end of the list. So, if we need to delete the last node of the list we just mark the last node as sentinel node.
Problem: Implement the list that uses a sentinel node to mark end of list and rewrite the delete operation by using sentinel node so that it always completes in constant time.