Linked Lists

A linked list is a very effective and efficient dynamic data structure for linear lists. Items may be added or deleted from it at any position more easily as compared to arrays which is a static data structure and adding and deleting of elements require lot of data movement.

Arrays contain consecutive memory locations that are a fixed distance apart, whereas linked lists do not necessarily contain consecutive memory locations. To maintain the specific sequence of these data items, we need to maintain link(s) with a successor (and/ or a predecessor). It is called as a linked list as each node is linked with its successor (and/ or predecessor).

 

A linked list is an ordered collection of data in which each element (node) contains a minimum of two values, data and link(s) to its successor (and/or predecessor). A list with one link field using which every element is associated to its successor is known as a singly linked list (SLL).

Each node of the linked list has at least the following two elements:

1. The data member(s) being stored in the list.

2. A pointer or link to the next element in the list.

The last node contains a null pointer to indicate it as tail or end of the list.

Linked lists are generally implemented using dynamic memory management. Each linked list has a head pointer that refers to the first node of the list and the data nodes storing data member(s). The linked list may have a header node, tail pointer, and so on.

Header node A header node is a special node that is attached at the beginning of the linked list. This header node may contain special information (metadata) about the linked list.

Tail pointer is a pointer pointing to the last node of a linked list.

 

The following are basic operations of linked list as a data structure:

1. Creating an empty list

2. Inserting a node

3. Deleting a node

4. Traversing the list

Some more operations are:

5. Searching a node

6. Updating a node

7. Printing the node or list

8. Counting the length of the list

9. Reversing the list

10. Sorting the list using pointer manipulation

11. Concatenating two lists

12. Merging two sorted lists into a third sorted list

 

Linked List abstract data type

Linked list can be implemented in a variety of ways, the most flexible implementation is by using pointers.

Each linked list has to have a special external link (or pointer), say, Head. It is an external link because it is not stored in the list.

 

To represent this linked list, the definition is

class LList

{

private:

Node *Head,*Tail;

 

public:

LList();

~LList();

:

//member functions here

:

};

 

The LList class has only one data member, the Head pointer, which points to the first node of the list, which is used to access the list. The member functions including the constructor and the destructor are used to process the list.

Data structure of node

Each node has data and link fields. The data field holds data element(s) and the link field(s) stores the address of its successor (and/or predecessor).

The declaration of the data structure of a node is given as follows:

class Node

{

public:

int data;

Node *link;

};

I. Insertion of a node

Insertion can be made at the beginning, middle, or at the end of the list.

a. Insertion of a Node at a Middle Position

Let Prev refer to the node after which NewNode node is to be inserted. The successor of Prev will be the successor of the NewNode. Set the link  field of the NewNode to the Prev’s successor node.

NewNode->link = Prev->link;

Now make NewNode the successor of Prev.

Prev->link = NewNode;

  

b. Insertion of a Node at the First Position

To insert a node at the first position, there will be no Prev node. Head is the pointer variable pointing to the starting node of the list. The insertion of NewNode at the first position should make Head point to NewNode, and in addition, the current node which is at the first position should become the second node of the list.

The following two steps will insert NewNode at the beginning of the linked list.

NewNode->link = Head;

Head = NewNode;

 

c. Insertion of a Node at the End

Here we have to traverse to the last node and Prev is the pointer to the last node. Make NewNode pointing to null.

 

Now make Prev node link pointing to NewNode.

Prev->link = NewNode;

This will make the node NewNode the successor of Prev.

II. Deletion of a Node

To delete a node the address of the node to be deleted as well as its predecessor has to be known to modify the links such that the node is deleted.

 

To delete node Curr the link between Curr and its previous node, and the link between Curr and its successor has to be modified.

A node can be deleted at first, middle or from the last of linked list.

a. Deleting the First Node

If the node at the first position is to be deleted, then we need to modify the pointer pointing to the first node (Head).

Set another pointer to the first node before modifying Head, which is the pointer pointing to the first node.

Curr = Head;

Set Head to point to the second node.

Head = Head->link;

Now, release the memory allocated for the first node (Curr).

delete Curr;

 

b. Deleting a Middle Node

Let curr point to the node to be deleted, and prev be the predecessor of curr. Then

prev->link = curr->link;

delete curr;

Above statements deletes the curr node.

 

c. Deleting the last node

To delete last node, make last node as curr and last nodes predecessor as prev.

prev->link = curr->link;

delete curr;

These statements will delete the last node