My Project - Video Waker Alarm
Get Video alarm on Google Play

Linked list – Structure, Operations, Types, Examples


Linked list – Structure, Operations, Types, Examples. A Linked list, also known as one way list, is a linear collection of data elements, called nodes, where the linear order is given by means of pointers. Linked list can be considered similar to array as both store data linearly. So why we are Linked list instead of array?

Why Linked List?

The most important drawback of array is that the array is a static structure; the allocation occurs during the compile time and hence cannot be extended or reduced. Linked list on the other hand have many advantages:

  • Linked list are dynamic data structure: Linked list can grow or shrink during the execution of the program.Linked lists allocate memory for each element separately and only when necessary.
  •  Efficient memory utilization: Unlike array, where pre-allocation waste memory, linked list on the other hand allocates memory whenever it is required as it is a dynamic data structure.
  •  Insertion and Deletion are easier and efficient: Linked List provides flexibility of inserting and deleting a node from the list.
  • Many complex applications can be easily carried out.

Structure of Linked list:

A list consists of linearly connected train of nodes. Each node can be divided into two parts:

  1. Data Field:It is the actual value that is stored and processed.
  2. Linked Field: It is the address of the next data item in the Linked List.
Linked list Structure
Linked list Structure

The entire linked list is accessed from an external pointer which points to the first node as shown in Fig 1.1. The external pointer is one which does not belong to the node. The last node of Linked list consist of a special value “null” which denotes the end of the linked list.

Linked List as a Self Referential Class:

typedefstructnode
{
int info; // will store value
node *next; // will store the reference
};

If p is a pointer to a node then node (p), the node pointed by p, info (p) refers to the information portion of the node and next (p) refers the next address.

Linked List
Linked List

Real time Example of Linked List Data Structure:

There are many real time application of Linked list. I have listed few of single linked list examples below:

  • Train: Train, starts from engine, and then coaches followed. You can traverse one coach to other, if it is connected to each other.
Linked list example Train
Linked list example Train
  • Hunt for problem Game: In this game, you need to hunt or search for the problem or thing. For this you will be given a single clue, which has some information and give you a direction for other clue, and this continues until you reach destination.
Linked list real time example
Linked list real time example
  • Steel Chain

What are the operations that can be performed on a Linked List?

The three basic operations that can be performed on a list are:

» Creation: This operation is used to create constituent node as and when required.

» Insertion: This operation is used to insert a new node in the linked list.

  • At the beginning of the list,
  • At a certain position and
  • At the end.

» Deletion: This operation is used delete node from the list.

  • At the beginning of the list,
  • At a certain position and
  • At the end.

Other Linked list common operation :

» Traversing: It is a process of going through all the nodes of a linked list from the end to the other end.

» Concatenation: The process of appending the second list to the end of the first list.

» Display: This operation is used to print each and every node’s information.

Types of Linked List:

» Singly linked list / Linear Linked List
» Doubly Linked List
» Circular Linked List
» Circular Doubly Linked List.

List C program implementation of Linked list:

Also you can see further programs, which use linked list to implement other data structure:

I would appreciate your comment, if you like to share more ideas related to the same topic.


3 thoughts on “Linked list – Structure, Operations, Types, Examples”

  1. Thank you …..
    I have got the Exact solution of my confusion……
    Especially the example of train was awesomeness….

Leave a Reply

Your email address will not be published. Required fields are marked *