Singly Linked List

Complete PPT About Singly Linked List, why use linked list over array, Different Operations of Linked List (Traversal, Insertion, Deletion)

1. LINKLIST
BY
MUKESHSAKLE
ASSISTANTPROFESSOR
DEPARTMENTOFINFORMATIONTECHNOLOGY
Raghav Birla

2. LINKEDLIST
A linked list is a linear data structure.
Nodes make up linked lists.
Nodes are structures made up of data and a
pointer to another node.

3. What is Linked List?
A linked list is a collection of nodes with various
fields
It contains data field and Address field or Link
field
Info field
Link Field/
Address
Field
Pointer to the
first node

4. Why Linked List?
What are the problems with Arrays
- Size is fixed
-Array Items are stored contiguously
-Insertions and deletion at particular position is
complex
Why Linked list ?
-Size is not fixed
-Data can be stored at any place
-Insertions and deletions are simple and faster

5. ARRAYSVSLINKEDLISTS
Arrays Linked list
Fixed size: Resizing is expensive Dynamic size
Insertions and Deletions are inefficient:
Elements are usually shifted
Insertions and Deletions are efficient: No
shifting
Random access i.e., efficient indexingNo random access
Not suitable for operations requiring
accessing elements by index such as sorting
No memory waste if the array is full or almost
full; otherwise may result in much memory
waste.
Since memory is allocated dynamically(acc. to
our need) there is no waste of memory.
Sequential access is faster [Reason: Elements in
contiguous memory locations]
Sequential access is slow [Reason: Elements not
in contiguous memory locations]

6. SINGLYLINKEDLIST
Each node has only one link part
Each link part contains the address of the next
node in the list
Link part of the last node contains NULL value
which signifies the end of the node

7. SCHEMATIC REPRESENTATION
Here is a singly-linked list (SLL):
a b c d
Start
•Each node contains a value(data) and a
pointer to the next node in the list
•Start is the header pointer which points at
the first node in the list

8. Graphical Representation
10
2000
2000
3000
3000
15
NULL
20
1000
Singly Linked List
Start=1000

9. STRUCTURE OF SINGLE LINKED LIST NODE
Struct node
{
int info;
Struct node * Next
} *start=NULL;

10. ACCESSINGTHESTRUCTURE MEMBERS
USINGPOINTER
structBook
{
char name[10];
intprice;
} ;
intmain()
{
structBookb;
structBook* ptr= &b;
ptr->name = “MS";
ptr->price = 500;
}

11. Allocation of memory to new_node
New_node=( Struct node *) malloc(sizeof(struct node));
It Returns address of the location with piece
of memory of the size struct. That is for
information field and address field

12. Operations of single linked list
Creation of node of link list
Insertion in a single linked list
Deletion from a single linked list
Searching in a single linked list
Reverse the single linked list

13. CREATINGANODE
structnode{
intdata; // A simple node of a linked list
structnode*next;
}*start; //start points at the first node
start=NULL ; initialisedto NULL at beginning

14. node* create( intnum) //say num=1 is passed from main
{
struct node*ptr;
ptr= new node; //memory allocated dynamically
if(ptr==NULL)
„OVERFLOW‟ // no memory available
exit(1);
else
{
ptr->data=num;
ptr->next=NULL;
return ptr;
}
}

15. TOBECALLEDFROMMAIN() AS:-
void main()
{
node* ptr;
intdata;
scanf(“%d”,&data);
ptr=create(data);
}

16. INSERTIONDESCRIPTION
Insertion at the front of the single list
Insertion at the end of the single list
Insertion after the particular node of the single list

17. INSERTIONATTHETOP
Steps:
Create a Node
Set the node data Values
Connect the pointers

18. INSERTIONDESCRIPTION
Follow the previous steps and we get
15 20 //Start 10
Step 1 Step 2
Step 3
1000 2000
4000
4000
10
15 20start //
200010004000

19. Functions to create new node of
linked list then inserting that
node in the front of linked list

20. Struct node* create-node( int num)
{
struct node* new-node;
new-node=(struct node* ) malloc ( sizeof (struct node));
if(newnode ==NULL)
{
„OVERFLOW‟ // no memory available
exit(1);
}
else
{
new-node->info=num;
new-node->link=NULL;
return new-node;
}
}
Node creation
Set the values of node

21. C Function to Insert an Element from the
front
Insertfront(struct node* start, int item)
{
struct node* temp = create-node(item);
temp->link=start;
start=temp;
return(start);
}
Create the node and
assign the values to
newnode in create-
node() function
Connect the pointers

22. 10
1000
1000
2000
2000
15 NULL20
4000
Operations on Singly Linked List
Insert from the front
Start = 1000
temp
temp->link=start,

23. 10
1000
1000
2000
2000
15 NULL20
4000
Operations on Singly Linked List
Insert from the front
Start=4000
start=temp

24. INSERTIONDESCRIPTION
Insertion at the top of the singlelist
Insertion at the end of the single list
Insertion after the particular node of the singlelist

25. INSERTIONATTHEEND
Steps:
Create a Node
Set the node data Values
Connect the pointers

26. INSERTIONDESCRIPTION
Follow the previous steps and we get
15 20 10
//Start
Step 1 Step 2
Step 3
1000 2000
4000
4000
10
15 20start //
20001000
4000

27. Functions to create new node of linked
list then inserting that node in the
last of linked list

28. Struct node* create-node( int num)
{
struct node* new-node;
new-node=(struct node* ) malloc(sizeof (struct node));
if(newnode ==NULL)
{
„OVERFLOW‟ // no memory available
exit(1);
}
else
{
new-node->info=num;
new-node->link=NULL;
return new-node;
}
}
Node creation
Set the values of node

29. C Function to Insert an Element at the end
Void Insert-End( struct node* start, int item)
{
struct node* temp = create-node(item);
if(start==NULL)
{
start=temp;
print”\n Node inserted successfully at the end…!!!\n”;
}
else {
q = start;
while(q->link!=NULL)
{ q=q->link; }
q->link=temp;
}
}
Connect the
pointers
Create the node and
assign the values to new-
node in create-node()
function

30. 10
1000
null
2000
2000
15 NULL20
4000
Operations on Singly Linked List
Insert at the end
Start = 1000
temp
q=start
While(q link != null)
q=q link
After calling
Create-node(10)

31. 15
2000
2000
4000
4000
20 NULL10
1000
Operations on Singly Linked List
Insert at the end
Start=1000
q link = temp
q
temp

32. void insert_at_end()
{
structnode *new_node,*current;
new_node=(structnode *)malloc(sizeof(structnode));
if(new_node== NULL)
printf("nFailedto Allocate Memory");
printf("nEnterthe data : ");
scanf("%d",&new_node>data);
new_node->next=NULL;
if(start==NULL)
{
start=new_node;
current=new_node;
}
else
{
temp = start;
while(temp->next!=NULL)
{
temp = temp->next;
}
Temp->next = new_node;
}
}

33. INSERTIONDESCRIPTION
Insertion at the top of the single list
Insertion at the end of the single list
Insertion after a particular node of the single list

34. INSERTIONAFTERAPARTICULAR NODE
Steps:
Create a Node
Set the node data Values
Break pointer connection
Re-connect the pointers

35. INSERTIONDESCRIPTION
Follow the previous steps and we get
15 10 20
//Start
Step 1 Step 2
Step 4
1000
2000
4000
2000
10
15 20start //
40001000
4000
15
20 //Start
Step 3
//
1000
2000

36. Functions to create new node of linked
list then inserting that node after a
particular node in the linked list

37. Struct node* create-node( int num)
{
struct node* new-node;
new-node=(struct node* ) malloc ( sizeof (struct node));
if(newnode ==NULL)
{
„OVERFLOW‟ // no memory available
exit(1);
}
else
{
new-node->info=num;
new-node->link=NULL;
return new-node;
}
}
Node creation
Set the values of node

38. C Function to Insert an Element with data value item after the i
node
Insert-after(struct node* start, int item, inti)
{
struct node* temp = create-node(item);
Struct node* q;
q=start;
for( loc=1;loc<i;loc++)
{
q=q link;
if(q==NULL)
print ”Less than „i” nodes in the list…!!!”;
}
temp link=q->link;
q link=temp;
Connect the
pointers
Create the node and
assign the values to new-
node in create-node()
function

39. 10
1000
null
2000
5
4000
Operations on Singly Linked List
Insert after a particular node
Start = 1000
temp
If i=2 then
q=start
for( loc=1;loc<i;loc++)
q=q link;
After calling
Create-node(10)
2000
300015
3000
NULL20

40. Insert after a particular node
15
4000
4000
3000
3000
10 NULL20
2000
Start=1000
2. q link=temp;
15
4000
3000
3000
300010 NULL20
2000
Start=1000
1. temp link=q->link;
q
temp
1000
20005
1000
20005
q temp

41. DELETIONDESCRIPTION
Deleting from the top of the single list
Deleting from the end of the single list
Deleting after the particular node of the single list

42. DELETIONDESCRIPTION
Deleting from the top of the single list
Deleting from the end of the single list
Deleting after the particular node of the single list

43. DELETINGFROMTHETOP
Steps
Break the pointer connection
Re-connect the nodes
Delete the node

44. DELETIONDESCRIPTION
15 20
start
10
15 20
start
10
15 20
start
1

45. Functions to delete the front node from
the linked list

46. Struct node* del-first(struct node* start)
{
if(start == NULL)
print ”Error……List is empty”;
else
{
struct node* temp;
temp=start;
start=temp->link;
delete temp;
} return start;
}
temp is the node to be
deleted
Otherwise update start
with new start
Delete the node
If (start link = null)
Start=null and return start;
Check if list has single element

47. 10
1000
1000
2000
2000
15 NUL
L
20
4000
Operations on Singly Linked List
Delete from the front
Temp=Start = 4000
temp=start

48. 10
1000
1000
2000
2000
15 NULL20
4000
Operations on Singly Linked List
Delete from the front
Start=1000
temp
temp=start, start=temp->link

49. 1000 2000
2000
15 NULL20
Operations on Singly Linked List
Delete from the front
start
Delete the node temp

50. DELETIONDESCRIPTION
Deleting from the top of the single list
Deleting from the end of the single list
Deleting after the particular node of the single list

51. DELETINGFROMTHEEND
Steps
Break the pointer connection
Set previous node pointer to NULL
Delete the node

52. DELETIONDESCRIPTION
15 20
start
10
15
start
2010
1510
start

53. Functions to delete the last node from
the linked list

54. Struct node* del-last(struct node* start)
{
if(start==NULL)
print ”Error….List is empty”;
else
{
struct node* q=start;
while(q link link!=NULL)
q=q link;
struct node* temp = q link;
q link=NULL;
delete temp;
}
} return start
}
Store the node to be
deleted in temp and Set
link part of 2nd
Node to NULL
Delete the node
Finding the location
of 2
nd
last node
If (start link = null)
Start=null and return start;
Check if list has single element

55. 10
1000
1000
2000
2000
15 NULL20
4000
Operations on Singly Linked List
Delete from the last
Temp=Start = 4000
struct node* q=start;
while(q link link!=NULL)
q=q link;

56. 10
1000
1000
2000
NULL
15 NUL
L
20
4000
Operations on Singly Linked List
Delete from the last
Start=4000
temp
struct node* temp;
temp = q link;
q link=NULL;
q

57. Operations on Singly Linked List
Delete from the last
4000 1000
1000
10 NULL15
start
Delete the node temp

58. DELETIONDESCRIPTION
Deleting from the top of the single list
Deleting from the end of the single list
Deleting node after the particular node of the single list

59. DELETINGNODEAFTERTHEPARTICULAR
NODE
Steps
Set previous Node pointer to next node
Break Node pointer connection
Delete the node

60. DELETIONDESCRIPTION
10 15 20
head
10 17
head
20
10
head
20

61. Functions to delete the node after the
particular node from the linked list

62. Struct node* del-after( struct node* start, intdata)
{
Struct node* q = start, *temp;
while( qinfo ! = data|| q link != null)
{
q = q link; // q is the node with info as data
}
if (q info = data && q link != null)
{
temp = q link // temp is the node to be deleted
q link = temp link; // rearrange the pointers
delete( temp );
}
Else
Print “no such node exist”
Function to delete a node after the node with node-info value as
data

63. 10
1000
1000
2000
2000
15 NULL20
4000
Operations on Singly Linked List
Delete after a particular node
Temp/Start
= 4000
suppose data = 10
while( qinfo ! = data|| q link != null)
{
q = q link; // q is the node with info as data
}

64. 10
1000
2000
2000
2000
15 NULL20
4000
Operations on Singly Linked List
Delete after a particular node
Start=4000
temp
if (q info = data && q link != null)
{
temp = q link // p is the node to be deleted
q link = temp link; // rearrange the pointers
delete( temp );
}
Else
Print “no such node exist”
q

65. Operations on Singly Linked List
Delete after a particular node
4000 2000
2000
10 NULL20
start
Delete the node temp

66. SEARCHING ASINGLELINKEDLIST(SLL)
Searchinginvolvesfindingtherequiredelementinthelist
Wecanusevarioustechniquesofsearchinglikelinearsearchor
binarysearchwherebinarysearchismoreefficientincaseof
Arrays
Butincaseoflinkedlistsincerandomaccessisnotavailableit
wouldbecomecomplextodobinarysearchinit
Wecanperformsimplelinearsearchtraversal

67. In linear search each node is traversed till the data in
the node matches with the required value
void search(struct node* start, int x)
{
struct node* temp = start;
while(temp!=NULL)
{
if( temp data==x)
{
print “FOUND ”<< temp->data;
break;
}
temp=temp->next;
}
}

68. REVERSINGALINKEDLIST
•We can reverse a linked list by reversing the direction
of the links between 2 nodes

69. We make use of 3 structure pointers say p,q,r
At any instant q will point to the node next to p and r will point to
the node next to q
NULL
Head P q r
NULL
•For next iteration p=q and q=r
•At the end we will change head to the last node
p q

70. CODE
{
node*temp,*prev,*curr;
if(start==NULL)
{
print "List is empty";
return;
}
prev=null;
curr=null
temp=start;
while(temp!=NULL)
{
prev=curr
curr=temp
temp=templink
curr->link=prev;
}
start=curr;
return start;
}
Struct node* reverse(struct node * start)