What are Linked Lists ? - data structure tutorial

What are Linked Lists ? - data structure tutorial

A linked list is a sequence of data structures that are associated together by means of connections or links.

Linked List is a sequence of linked which contains things. Each link contains a connection to another link. A linked list is the second most utilized data structure after arrays.

The following are significant terms to understand the ideas of Linked List.

•  Link − Each Link of a link list can store information called an element.
•  Next − Each Link of a link list contains a link to the next node called Next. 
•  Node – It is a block in memory that has 2 parts as mentioned below (Linked Lists in Data Structures).

Linked List Representation

Here, every node contains a data port (the upper piece of the image) and connection to another node(lower part of the image). Notice that the last node doesn't point to any node and just stores NULL. In C++, we accomplish this functionality by utilizing structures and pointers. Each structure represents a node having some data and furthermore a pointer to another structure of a similar kind. This pointer holds the location of the next node and makes the connection between two nodes. So, the structure is something like:

struct node

{

    int data;

    struct node *next;

};

The main data member the structure (named node) is an integer number to hold an integer and the second part is the pointer to a node (same structure). This implies the second part holds the location of the next node in this way, each node is associated as spoke to in the image above.

 The image speaking to the above structure is given below.

Thus, if we access the first node, at that point we can access any node of the linked list. For example, if 'a' is the node then a->next is the node next to 'a' (the pointer storing the location of the next node is named 'next'). One thing you should see here is that we can easily access the next node but there is no way of getting to the past node and this is the limitation (Linked Lists in Data Structures).

Basic Operations

The following are the fundamental operations of a link list.

• Insertion − to add elements to the link list.

• Deletion − to delete elements from the link list.

• Search − to search a value in the link list.

• Delete − delete an element by the given key.

Insertion Operation

Insertion is a three-step process −

• Create a new Link with provided data.
• Point New Link to old First Link.
• Point First Link to this New Link.

• //insert link at the first location • void insertFirst(int key, int data){ • //create a link • struct node *link = (struct node*) malloc(sizeof(struct node)); • link->key = key; • link->data = data; • • //point it to old first node • link->next = head; • • //point first to new first node • head = link; • • }

Deletion Operation

Deletion is a two-step process −

• Get the Link pointed by the First Link as Temp Link.
• Point First Link to Temp Link's Next Link.

//delete first item struct node* deleteFirst(){ //save reference to first link struct node *tempLink = head; //mark next to first link as first head = head->next; //return the deleted link return tempLink; }

Navigation Operation

Navigation is a recursive procedure and is the basis of many operations like search, delete and so on −

•           Get the Link pointed by the First Link as Current Link.

•           Check if Current Link is not NULL and display it.

•           Point Current Link to Next Link of Current Link and move to the above step (Linked Lists in Data Structures?).

//display the list void printList(){ struct node *ptr = head; printf("\n[ "); //start from the beginning while(ptr != NULL){ printf("(%d,%d) ",ptr->key,ptr->data); ptr = ptr->next; } printf(" ]"); }

Advanced Operations

The following are the advanced operations specified for a list.

·      Sort − sorting a list based on a particular order.

·      Reverse − reversing a linked list.

• void sort(){ • • int i, j, k, tempKey, tempData ; • struct node *current; • struct node *next; • int size = length(); • k = size ; • • for ( i = 0 ; i < size - 1 ; i++, k-- ) { • current = head ; • next = head->next ; • • for ( j = 1 ; j < k ; j++ ) { • • if ( current->data > next->data ) { • tempData = current->data ; • current->data = next->data; • next->data = tempData ; • • tempKey = current->key; • current->key = next->key; • next->key = tempKey; • } • • current = current->next; • next = next->next; • } • } • }

Reverse Operation

The following code demonstrates reversing a single linked list.

void reverse(struct node** head_ref) { struct node* prev = NULL; struct node* current = *head_ref; struct node* next; while (current != NULL) { next = current->next; current->next = prev; prev = current; current = next; } *head_ref = prev; }

Types of Linked List

The following are the various types of the linked list.

• Simple Linked List − Item navigation is forward only.
• Doubly Linked List − Items can be navigated forward and backward.
• Circular Linked List − the Last item contains a link of the first element as next and the first element has a link to the last element as previous.

The next post will see the doubly linked list (What are Linked Lists ? - data structure tutorial).

Till then try out the following programs based on the linked list which were asked in interviews by many software companies:

1.  WAP to delete a middle element of a linked list. 
2.  WAP to swap alternate elements of a linked list pairwise.
3.  WAP to delete duplicate elements of a linked list.
4.  WAP to search a key in a linked list.
5.  WAP to reverse a linked list.
6. WAP to rotate a linked list clockwise.
7.  WAP to find the nth node from the end of a linked list.
8.  WAP to swap a node with its previous node.
9.  WAP to sort a linked list. 
10.   WAP to print Middle of a given linked list.

Comment if you are unable to solve any of the above programs. I will definitely answer it in the next post.