Linked List

This tutorial explains about linked List concept. it contains types of linked list also. All possible graphical representations are included for better understanding.

1. Prepared By:
Dr. Chandan Kumar
Assistant Professor, Computer Science & Engineering Department
Invertis University, Bareilly

2. Introduction
A linked list is a linear data structure which is used to store
a collection of elements.
Each element in a linked list is represented by node.
It is a best example of dynamic data structure that uses
pointer for the implementation
Each node contain two parts
Data part or info part -which is used to store the element
Link part or address part-which is used to stores the link to
the next node.
Node
Data Link

3. Introduction
Linked list require more memory compare to array for
the same size of the elements because along with data
or value it also store pointer to next node.
It is the most common and simplest data structure.
They can be used to implement other data structure
like stack and queue etc.
Finally, we can say that a linked list is a set of
dynamically allocated nodes, organizedin
suchawaythateachnodehasavalueandapointer.

4. Introduction
ArraysandLinkedListsarebothlineardatastructures
sotheydohavesomeadvantagesanddrawbacksover
eachother.
Now let us look at the difference between arrays and
linked list.

5. Arrays Vs Linked List
Arrays Linked Lists
Collection of elements of
similar data type
Support random access using
indexing
Best suitable for fixed size
elements implementation
Insertion and deletion of
elements are inefficient i.e.
elements are usually shifted
An ordered collection of
elements of the same type
where each element is
linkedusingpointerstothe
nextone.
Doesn’t support random
access
Support Dynamic size
Insertion and deletion of
elements are efficient i.e. no
shifting

6. Arrays Vs Linked List
Arrays Linked Lists
Memory is allocated
statically or compile time
Wastage of memory if the
allocated memory is not fully
utilized
Data elements are stored in
computer memory in
contiguous location; so access
is faster
Size must be specified at the
time of array declaration
Memory is allocated
dynamically or run time
There is no wastage of memory
Newelementscanbestored
anywhere,anduse pointers
tocreateareferenceforthe
newelement; so access is slow
Size of a Linked list
grows/shrinks as and when new
elements are inserted/deleted.

7. Types of Linked List
There are two types of linked list
Single or Singly linked list (SLL)
Single Circular Linked List
Double or Doubly linked list (DLL)
Double Circular Linked List

8. Singly Linked List (SLL)
This is a fundamental type of linked list
Each node has two part
Data or info part-contain actual value or information
Next or link part –contain pointer or address of the next node
Last node contain NULL value in link part which indicated
end of the node
Traversing is allowed only in forward direction
It uses less memory as compare to doubly linked list per
node ( Single pointer)

9. Singly Linked List (SLL)
Complexity of insertion and deletion at a known
position is O(n)
We prefer SLL If we need to save memory and
searching is not required
Singly linked list can mostly be used for stacks

10. Singly Linked List (SLL)
For Example
Theabovefigureshowsasinglylinkedlist.Thefirstnode
isalwaysusedasareferencetotraversethelistandis
calledHEAD.ThelastnodepointstoNULL.

12. Singly Linked List (SLL)
ASingly linkedlistcanbeimplementedin C
programming langauge using the structure and
thepointer.
struct LinkedList
{
int data;
struct LinkedList *next;
};
This definition is used tobuild
everynodeinthelist.
Thedatafieldstorestheelement,
andthenext field is a pointer to
storethenextnode'saddress.

13. Implementation of SLL in C language
#include<conio.h>
#include<stdio.h>
void main()
{
structnode
{
intvalue;
structnode *next;
}*a,*b,*c;
clrscr();
a->value=5;
b->value=6;
c->value=7;

14. Implementation of SLL in C language
a->next=b;
b->next=c;
c->next=NULL;
printf("\nNodea\n value=%d and Next =%u",a->value,a->next);
printf("\nNodeb\n value=%d and next =%u",a->next->value,a-
>next->next);
printf("\nNodec\n value=%d and next=%u",a->next->next-
>value,a->next->next->next);
getch();
}

15. Output

16. Single Circular Linked List
Each node has two parts like SLL
No beginning and No end
Does not contain NULL pointer like SLL
Last node is connected to first node i.e. link part of last
node contain address of first node
Traversing allowed only in forward direction
Time saving when we want to go from last node to first
node
A good example where it is used is a timesharing
problem solved by operating system

17. Single Circular Linked List
For example

18. Doubly Linked List (DLL)
Each node has three parts, one data part and two link
part
Data part contain actual value
One link part contain next pointer to point next node
Another link part contain previous pointer to point
previous node

19. Doubly Linked List (DLL)
// C language to represent a node for DLL
struct node
{
int info;
struct node *next;
struct node *prev;
};

20. Doubly Linked List (DLL)
Traversing is possible in both directions i.e. forward and
backward directions
Required more memory as compare to SLL for the same
size ( two pointers required)
Previous link part value of first node and next link part
value of last node has value NULL
Complexity of insertion and deletion at a known position is
O(1)
We prefer DLL If we need better performance while
searching and memory is not a limitation
Can be used to implement stacks, heaps, binary trees

21. Doubly Linked List (DLL)
For Example:

22. Doubly Circular Linked List
Each node has three parts like DLL
No beginning and No end
Does not contain NULL pointer like DLL
First node is connected to the last node and Last node is
connected to first node i.e. previous pointer of the first
node contain address of last node and next pointer of last
node contain address of first node
Traversing allowed in both directions i.e. forward and
backward directions
Time saving when we want to go from last node to first
node and vice versa

23. Doubly Circular Linked List
For example

24. Operation performed on Linked List
The operations which can be performed on a linked list
follow:
1.Creation
2.Insertion
3.Deletion
4.Traversing
5.Searching
6.Concatenation
7.Display

25. Creation
This operation is used to create a linked list
Memory allocated for nodes
Creating first node
head = (node*) malloc (sizeof(node));
head -> data = 50;
head -> next = NULL;

26. Insertion
Used to insert a new node in the linked list
Insertion take place at different places such as
At beginning of the linked list
At the end of the linked list
At specified position i.e. between any two nodes
Inserting a node is a more than one step activity
Created node must be in same structure

27. Insertion
At beginning of the linked list
Here we want to add Node X
Before inserting Node X

28. Insertion
After inserting Node X
New Node becomes new head of the linked list and next pointer
points to the Node A

29. Insertion
At the end of the linked list
Here we want to add Node X
Before inserting Node X

30. Insertion
After inserting Node X
next pointer of Node D pointes to new Node X and the
value of next pointer of Node D becomes NULL

31. Insertion
At specified position i.e. between any two nodes
Here we want to add Node X between Node B and Node C
Before inserting Node X

32. Insertion
After inserting Node X
Here, next pointer of Node B pointes to new Node X and next
pointer of Node X pointes to Node C

33. Deletion
Used to delete a node from the list
Deletion take place at different places such as similarly
insertion operation
From beginning of the linked list
From the end of the linked list
From specified position i.e. between any two nodes
Deleting a node is a more than one step activity

34. Deletion
Here we want to delete third node i.e. Node C from the
linked list
Next pointer of node B points to Node D
Similarly other deletion process will be done

35. Traversing
It is a process of examine all nodes of linked list i.e.
one end to the other end
Recursive function is used to traverse a linked list in a
reverse order
Going through first node to last node is called forward
traversing
Going through last node to first node is called
backward traversing

36. Searching
Process to find a desired element in the linked list
Sequential or linear search is the most common search
used in linked list
Traverse all nodes one by one and matches with key
value
There are two outcomes
Search is successful, if desired element is found in the
linked list
Search is unsuccessful, is desired element is not found in
the linked list

37. Concatenation
Process of appending second list to the end of the first
list
After concatenation, the linked list size will increases
This is simply done by pointing next pointer of last
node of first linked list to first node of the second
linked list

38. Display
Used to print information of each nodes in a linked list
Also display complete linked list