Mark Pearl

General

Basically, a linked list is a collection of nodes. Each node in the list has two components – a components to store information about that node (i.e. data) and a component to store the next “linked” node. The last node in a linked list indicates that it does not have a “linked” node – usually by a null reference. The address of the first node is stored in a separate location, called the head or first.

singlelinkedlist

The code snippet below shows a basic structure of a node declaration in c++.

struct nodeType
{
    int data;
    nodeType *link;
};

The variable declaration is as follows…

nodeType *head;

Basic Operations of a Linked List

There are a few basic operations that are typically needed with a linked list

Search a list to determine whether a particular item is in the list Insert an item in the list Delete an item from the list Traversing/Searching a List

To traverse a linked list you need some way to move around the list. The *head is a pointer in the list, but you cannot use it to traverse the list because then you would loose a reference to the beginning of the list.

Typically to traverse the list, you will need to declare another pointer that follows the same declaration as head, but that is not critical if you change where it’s pointing to…

current = head;
while (current != NULL)
{
    cout << current->data << " ";
    current = current->link;
}

Item Insertion and Deletion

To insert a new node into a linked list, you need to do the following:

Create a new node Determine the position in the list that you want to insert it and assign it to current Make the new node is point to the same link that current is pointing to Make current now point to the new node In code, assuming current was at the correct position, then it would look something like this…

nodeType *newNode;

newNode = new nodeType;
newNode->data = 123;
newNode->link = current->link;
current->link = newNode;

To delete a node from a linked list, you need to do the following:

Determine the node that you want to remove and point current to the node prior to that node Create a pointer to point to the node you want to delete (i.e. *p) Make current’s link now point to p’s link delete p from memory In code, assuming current was at the correct position, then it would look something like this…

deleteNode = new nodeType;
deleteNode = current->link;
current->link = deleteNode->link;
delete deleteNode;

Building a Linked List

There are two main ways to build a linked list, forward and backward.

I find the best way to explain this approach is code…. below if the forward approach, meaning the node is inserted forwards – i.e. at the back of the list…

int main()
{
    //
    // Init the list
    //
    nodeType *first;
    nodeType *last;
    nodeType *newNode;
    int num;

    first = NULL;
    last = NULL;

    //
    // Build the list the forward approach
    //
    for (int i=0; i<3; i++)
    {
        cout << "Enter number :";
        cin >> num;
        newNode = new nodeType;         // Create the new node
        newNode->data = num;            // and assign its data value
        newNode->link = NULL;           // make its link point to nothing
        if (first == NULL)              // If there is nothing in the list, then make the 
        {                               // newNode the first item and the last item
            first = newNode;
            last = newNode;
        }
        else                            // Else if first already has a value
        {                               // make the last item link to the newNode
            last->link = newNode;       // and make newNode the last item
            last = newNode;
        }
    }
    //
    // Display the list
    //
    DisplayList(first);
    system("PAUSE");
    return(0);
}

If you look at the forward approach, you need two pointers to maintain the list – first & last. This is because you don’t want to traverse the list each time you want to add something. The backward way of building a list in my opinion is easier to read and code since you only need to worry about the head of the list. The code implementation is listed below…

//
// Init the list
//
nodeType *head;    
nodeType *newNode;
int num;
head = NULL;    

//
// Build the list using the backward approach
//
for (int i=0; i<3; i++)
{
    cout << "Enter number :";
    cin >> num;
    newNode = new nodeType;         // Create the new node
    newNode->data = num;            // and assign its data value
    newNode->link = head;           // make its link point to the front of the list
    head = newNode;                 // make the head now be the newNode
}

Sorted & Unsorted Linked Lists

Typically there are two types of linked lists, those that are sorted and those that are unsorted.

The advantages of knowing that a collection of data is sorted when performing searches greatly reduces the complexity of the search algorithms as well as improving the searches performance.

Typically to maintain a sorted listed requires adjusting the insert method so that when a list is being built, the order is maintained.

Doubly Linked Lists

A doubly linked list is a linked list that every node has its “next” and “previous” node stored.

The advantages of a doubly linked list are that it can be traversed in any direction, which can be beneficial when performing iterations on the list.

The basic structure of a doublelinkedlist node is shown below…

struct doublenodeType
{
    int data;
    nodeType *next;
    nodeType *previous;
};

Circular Linked Lists

As the name suggest, a circular linked lists is one where the first node points to the last node of the list.



blog comments powered by Disqus

Want to get my personal insights on what I learn as I learn it? Subscribe now!


/