What is a Linked List?

When a set of items is organized sequentially, it is termed as list. Linked list is a list whose order is given by links from one item to the next. It contains a link to the structure containing the next item so we can say that it is a completely different way to represent a list. In linked list, each structure of the list is known as node and it consists of two fields (one for containing the item and other one is for containing the next item address).

An array is a best example for describing the list. In array, elements have been manipulated by using the index. Index is an implicit way of organizing an array. But there is a major issue with array that from the beginning, the size of an array has to be specified. For many real world time applications it may not be possible to specify the size. So that, linked list has been used in so many applications as it is a logical collection of links. These links (logical) are stored themselves as a part of data in structure by itself.

There are so many advantages of using linked list as it is a type of dynamic data structure where memory consumption has been allowed. There is no issue of a size as we can set any length for programming as required. It consumes less memory space for storing data. It is flexible in nature, as if we want to arrange, delete or add any items we can do it easily. Along with the quality of this linked list there is some issues also stands with it as linked list is very time consuming. When we do work for a fixed length type of list, it is quite good of using an array instead of linked list. It uses more storage area compared to array because each item of linked list contains an additional type of link filed.

For modeling, various types of abstract data type, linked list concept is very useful. For example in case of queues, trees and stacks, linked list can be merged with them in order to perform various operations. During the process, restriction is provided at insertion to one stage and deletion to other stage than queue modeled with the first in first out list.  Similarly, during process, restriction is done at both insertion and deletion only at one stage than stack modeled with push-down or last in first out lists. Two-dimensional linked list has been presented by trees, for example sport tournament’s chart.

Let us consider an example for understanding the proper concept for linking. A structure has been defined below:

Struct link_list

{

Float age:

Struct link_*next;

};

• Assuming two nodes named as x and y has been containing by list.

Struct link_list x, y;

Here x and y each containing two types of field (empty) as it creates a space for statement.

• Now x creates a link with y.

x.next = &y;

the address of y has been stored into the field of x.next by the statement. So that link has been created between the x and y.

• Now it is a time to assign filed age values.

x.age = 44.99;

y.age = 49.00;

• By creating a linked list for any number values we may allow process continuation.

y.next =  &z;

Another link “z” has been announced as a stuct link list variable.

There are some points to remember as:

• Every linked list has limitation as it has to be ended on one point.
• This happens by indicating on the end of any linked list.
• This is very necessary point in accessing any list.
• Null, it is a special value of any pointer in C language.

y.next = 0;

Null value has been stored in the last node’s next field.

• So the final linked list has been shown below:

printf("%fn”, x.nextàage);

The value of the number of age y can be accessed by using the next member of x.

Types of Linked List:

There are various types of a linked list (singly linked list) but mainly three types have been considered.

• Circular linked list: There is not an issue of starting point and ending point as there is a circle between first and last time.
• Double linked list: It is not similar to a circular linked as there is double set for pointer has been defined. Step by step link has been followed as one item is connected to other item and so on. It follows the rule of traversing.
• Circular doubly linked list: Both types of processing (forwarding and back warding) have been followed in circular doubly linked list.

Operations in Linked List

In Linked list we can perform various types of operations like creation of a list, traversing a list, count the number of items, printing the list or the sub-list, editing work for an item, insertion of an item, deletion of an item and concatenation of two different of lists. We can attach and delete data at constant time in link list.

Some Important Keywords

There are some important terms to remember in linked list named as sizeof, malloc, calloc, null, free. These terms or functions can be used for determining or performing an operation.

• size of: size of a linked list van be determined by using this operator.
• malloc: it can be used during memory location. While performing any operation if null value occurred, malloc operator can be used for testing it.
• calloc: it can be used during memory location. While performing any operation if null value has been occurred, malloc operator can be used for testing it.
• free: for releasing the memory free function has been used.
• null: it is an initialization for nothing.

Pointers can play a vital role while performing any linked list operation. While processing of a linked list some pointers are used broadly. For specifying any data item, variables can be stated as variable.

• Initialization: p=&x; q=&y;

Here x’s address has been contained by the pointer p and y’s address has been contained by the pointer q.

• Assignment: p=q;

Address of the y’s variable has been assigned to the p’s pointer variable.

• Assignment *p=*q

Location of the p has been pointed out by the location of q variable.

• p=0; q=0;

Null variable has been initialized nothing.

Context and Applications:

This topic is significant in the professional exams for both undergraduate and graduate courses, especially for      

• BCA
• B.Sc Computer Science
• M.Sc Computer Science