2. Linked Lists.pdf.data.structure.algorithm

data structure

1. Linked Lists
1
DATA STRUCTURES
AND ALGORITHMS

2. LIST ADT
•What we mean by a "list".
•It is a collection of some elements.
•The most important concept related to lists is that
ofposition. In other words, we perceive that there is a first
element in the list, a second element, and so on.
•So, we consider alistto be a finite, ordered sequence of data
items known aselements.
•This is close to the mathematical concept of asequence.
2

3. LIST ADT
•"Ordered"inthisdefinitionmeansthateachelementhasa
positioninthelist.
•Sotheterm"ordered"inthiscontextdoesnotmeanthatthelist
elementsaresortedbyvalue.
•Eachlistelementmusthavesomedatatype.
•Althoughthereisnoconceptualobjectiontolistswhoseelements
havedifferingdatatypesiftheapplicationrequiresit.
3

4. LIST ADT
•A list is said to beemptywhen it contains no
elements.
•The number of elements currently stored is called
thelengthof the list.
•The beginning of the list is called thehead, the end
of the list is called thetail.
4

5. Basic Operations on LIST ADT
•A list should be able to grow and shrink in size as we insert and
remove elements.
•We should be able to insert and remove elements from anywhere
in the list.
•We should be able to gain access to any element's value, either to
read it or to change it.
•We must be able to create and clear (or reinitialize) lists.
•It is also convenient to access the next or previous element from
the "current" one.
5

6. Implementations of LIST ADT
•There are two standard approaches to implementing lists:
•thearray-based list,
•and thelinked list.
•We have already learnt about arrays in detail.
•Now, we will discuss about:
•What linked-list is?
•What are its types?
6

7. Need for Linked List
•Sometimes you need to store a list of elements in memory.
•Suppose you’re writing an app to manage your to-do's.
•You’ll want to store the to-do's as a list in memory.
•Let’s store the to-do's in an array.
7
■Using an array means all your tasks
are stored contiguously (right next
to each other) in memory.

8. Need for Linked List
•Now suppose you want to add a fourth task.
•But the next location is taken up by someone else’s stuff!
•You have to move to a new spot where you all fit.
8
■In this case, you need to ask your
computer for a different chunk of memory
that can fit four tasks.
■Then you need to move all your tasks
there.

9. Need for Linked List
•Similarly, adding new items to an array can be a big pain.
•If you’re out of space and need to move to a new spot in memory
every time, adding a new item will be really slow.
9
■One easy fix is to “hold seats”: even if you
have only 3 items in your task list, you can
ask the computer for 10 slots.
■Then you can add 10 items to your task list
without having to move.

10. Need for Linked List
•This is a good workaround, but you should be aware of a couple of
downsides:
10
You may not need the extra slots that you
asked for, and then that memory will be
wasted. You aren’t using it, but no one else
can use it either.
You may add more than 10 items to your
task list and have to move anyway.

11. Need for Linked List
•Linked lists solve this problem.
•With linked lists, your items can be anywhere in memory.
•Each item stores the address of the next item in the list.
11
■A bunch of random memory addresses are
linked together.

12. Need for Linked List
•Linked lists solve this problem.
•With linked lists, your items can be anywhere in memory.
•Each item stores the address of the next item in the list.
12
■A bunch of random memory addresses are
linked together.

13. Need for Linked List
•You go to the first address, and it says, “The next item can be found at
address 123.”
•So you go to address 123, and it says, “The next item can be found at
address 847,” and so on.
13
■With linked lists, you never have to move
your items.

14. Linked List
•A linked list is a sequence of data structures, which are connected
together via links.
•Each link contains a connection to another link.
14
■So, it is not just the “actual” value that is
stored; we also store the address of the
next location.
■Lets call this location as “node” which
contains two parts:
–The actual “data”
–The “pointer” to the next node.
5
datapointer
node

15. 15
A Simple Linked List Class
•We use two classes: Nodeand List
•Declare Node class for the nodes
•data: double-type data in this example
•next: a pointer to the next node in the list
class Node {
public:
int data; // data
Node* next; // pointer to next
};

16. Linked List
•It can be visualized as a chain of nodes, where every node points to the
next node.
•There are actual three nodes here; “head” is the pointer that points to
the first node.
•The last node points to “nowhere” or NULL, indicating the end of list.
16

17. 17
A Simple Linked List Class
•Declare List, which contains
•head: a pointer to the first node in the list.
Since the list is empty initially, headis set to NULL
•Operations on List
class List {
public:
List(void) { head = NULL; } // constructor
~List(void); // destructor
bool IsEmpty() { return head == NULL; }
Node* InsertNode(int index, int x);
int FindNode(int x);
int DeleteNode(int x);
void DisplayList(void);
private:
Node* head;
};

18. Operations on Linked List
1.Searching/Traversing
2.Updation
3.Inserting
1.In empty list
2.In front of list
3.In the middle of list
4.At the end
4.Deleting
1.First Node
2.Middle node
3.Last node
18

19. Inserting a new node
Node* List::InsertNode(int index, double x) {
if (index < 0) return NULL;
int currIndex = 1;
Node* currNode= head;
while (currNode&& index > currIndex) {
currNode = currNode->next;
currIndex++;
}
if (index > 0 && currNode== NULL) return NULL;
Node* newNode= new Node;
newNode->data= x;
if (index == 0) {
newNode->next= head;
head = newNode;
}
else {
newNode->next= currNode->next;
currNode->next= newNode;
}
return newNode;
}
Try to locate index’th
node. If it doesn’t exist,
return NULL.

20. Inserting a new node
Node* List::InsertNode(int index, double x) {
if (index < 0) return NULL;
int currIndex = 1;
Node* currNode= head;
while (currNode&& index > currIndex) {
currNode = currNode->next;
currIndex++;
}
if (index > 0 && currNode== NULL) return NULL;
Node* newNode= new Node;
newNode->data= x;
if (index == 0) {
newNode->next= head;
head = newNode;
}
else {
newNode->next= currNode->next;
currNode->next= newNode;
}
return newNode;
}
Create a new node

21. Inserting a new node
Node* List::InsertNode(int index, double x) {
if (index < 0) return NULL;
int currIndex = 1;
Node* currNode= head;
while (currNode&& index > currIndex) {
currNode = currNode->next;
currIndex++;
}
if (index > 0 && currNode== NULL) return NULL;
Node* newNode= new Node;
newNode->data= x;
if (index == 0) {
newNode->next= head;
head = newNode;
}
else {
newNode->next= currNode->next;
currNode->next= newNode;
}
return newNode;
}
Insert as first element
head
newNode

22. Inserting a new node
Node* List::InsertNode(int index, double x) {
if (index < 0) return NULL;
int currIndex = 1;
Node* currNode= head;
while (currNode&& index > currIndex) {
currNode = currNode->next;
currIndex++;
}
if (index > 0 && currNode== NULL) return NULL;
Node* newNode= new Node;
newNode->data= x;
if (index == 0) {
newNode->next= head;
head = newNode;
}
else {
newNode->next= currNode->next;
currNode->next= newNode;
}
return newNode;
}
Insert after currNode
newNode
currNode

23. Insert a Value
232323
19 0 4 12 15 NULL
Head
CurrentNode
5
Algorithm InsertNode(Position, Value)

24. Insert a Value
24
5
19
0
4
12
NULL
HeadPosition = 0
Value = 10
Node* List::InsertNode(int index, double x) {
if (index < 0) return NULL;
int currIndex = 1;
Node* currNode= head;
while (currNode&& index > currIndex) {
currNode = currNode->next;
currIndex++;
}
if (index > 0 && currNode== NULL) return NULL;
Node* newNode= new Node;
newNode->data= x;
if (index == 0) {
newNode->next= head;
head = newNode;
}
else {
newNode->next= currNode->next;
currNode->next= newNode;
}
return newNode;
}

25. Insert a Value
25
5
19
0
4
12
NULL
HeadPosition = 0
Value = 10
return NULL
Node* List::InsertNode(int index, double x) {
if (index < 0) return NULL;
int currIndex = 1;
Node* currNode= head;
while (currNode&& index > currIndex) {
currNode = currNode->next;
currIndex++;
}
if (index > 0 && currNode== NULL) return NULL;
Node* newNode= new Node;
newNode->data= x;
if (index == 0) {
newNode->next= head;
head = newNode;
}
else {
newNode->next= currNode->next;
currNode->next= newNode;
}
return newNode;
}

26. Insert a Value
26
5
19
0
4
12
NULL
HeadPosition = 1
Value = 10
Node* List::InsertNode(int index, double x) {
if (index < 0) return NULL;
int currIndex = 1;
Node* currNode= head;
while (currNode&& index > currIndex) {
currNode = currNode->next;
currIndex++;
}
if (index > 0 && currNode== NULL) return NULL;
Node* newNode= new Node;
newNode->data= x;
if (index == 0) {
newNode->next= head;
head = newNode;
}
else {
newNode->next= currNode->next;
currNode->next= newNode;
}
return newNode;
}

27. Insert a Value
27
5
19
0
4
12
NULL
HeadPosition = 1
Value = 10
Algorithm InsertNode(Position, Value)
If Position < 1 Then return NULL
CurrentNode=Head
CurrentPos=1
While CurrentNode!= NULL
If CurrentPos== Position Then break
CurrentPos++
CurrentNode= CurrentNode.Next
End while
If CurrentNode== NULL Then return NULL
Create New Node NewNode
NewNode.Data= Value
If Position == 1
NewNode.Next= Head
Head = NewNode
Else
NewNode.Next= CurrentNode.Next
CurrentNode.Next= NewNode
End If

28. Insert a Value
28
5
19
0
4
12
NULL
HeadPosition = 1
Value = 10
Algorithm InsertNode(Position, Value)
If Position < 1 Then return NULL
CurrentNode=Head
CurrentPos=1
While CurrentNode!= NULL
If CurrentPos== Position Then break
CurrentPos++
CurrentNode= CurrentNode.Next
End while
If CurrentNode== NULL Then return NULL
Create New Node NewNode
NewNode.Data= Value
If Position == 1
NewNode.Next= Head
Head = NewNode
Else
NewNode.Next= CurrentNode.Next
CurrentNode.Next= NewNode
End If
Current
Node

29. Insert a Value
29
5
19
0
4
12
NULL
HeadPosition = 1
Value = 10
Algorithm InsertNode(Position, Value)
If Position < 1 Then return NULL
CurrentNode=Head
CurrentPos=1
While CurrentNode!= NULL
If CurrentPos== Position Then break
CurrentPos++
CurrentNode= CurrentNode.Next
End while
If CurrentNode== NULL Then return NULL
Create New Node NewNode
NewNode.Data= Value
If Position == 1
NewNode.Next= Head
Head = NewNode
Else
NewNode.Next= CurrentNode.Next
CurrentNode.Next= NewNode
End If
Current
Node
CurrentPos=1

30. Insert a Value
30
5
19
0
4
12
NULL
HeadPosition = 1
Value = 10
Algorithm InsertNode(Position, Value)
If Position < 1 Then return NULL
CurrentNode=Head
CurrentPos=1
While CurrentNode!= NULL
If CurrentPos== Position Then break
CurrentPos++
CurrentNode= CurrentNode.Next
End while
If CurrentNode== NULL Then return NULL
Create New Node NewNode
NewNode.Data= Value
If Position == 1
NewNode.Next= Head
Head = NewNode
Else
NewNode.Next= CurrentNode.Next
CurrentNode.Next= NewNode
End If
Current
Node
CurrentPos=1

31. Insert a Value
31
5
19
0
4
12
NULL
HeadPosition = 1
Value = 10
Algorithm InsertNode(Position, Value)
If Position < 1 Then return NULL
CurrentNode=Head
CurrentPos=1
While CurrentNode!= NULL
If CurrentPos== Position Then break
CurrentPos++
CurrentNode= CurrentNode.Next
End while
If CurrentNode== NULL Then return NULL
Create New Node NewNode
NewNode.Data= Value
If Position == 1
NewNode.Next= Head
Head = NewNode
Else
NewNode.Next= CurrentNode.Next
CurrentNode.Next= NewNode
End If
Current
Node
CurrentPos=1

32. Insert a Value
32
5
19
0
4
12
NULL
HeadPosition = 1
Value = 10
Algorithm InsertNode(Position, Value)
If Position < 1 Then return NULL
CurrentNode=Head
CurrentPos=1
While CurrentNode!= NULL
If CurrentPos== Position Then break
CurrentPos++
CurrentNode= CurrentNode.Next
End while
If CurrentNode== NULL Then return NULL
Create New Node NewNode
NewNode.Data= Value
If Position == 1
NewNode.Next= Head
Head = NewNode
Else
NewNode.Next= CurrentNode.Next
CurrentNode.Next= NewNode
End If
Current
Node
CurrentPos=1

33. Insert a Value
33
5
19
0
4
12
NULL
HeadPosition = 1
Value = 10
Algorithm InsertNode(Position, Value)
If Position < 1 Then return NULL
CurrentNode=Head
CurrentPos=1
While CurrentNode!= NULL
If CurrentPos== Position Then break
CurrentPos++
CurrentNode= CurrentNode.Next
End while
If CurrentNode== NULL Then return NULL
Create New Node NewNode
NewNode.Data= Value
If Position == 1
NewNode.Next= Head
Head = NewNode
Else
NewNode.Next= CurrentNode.Next
CurrentNode.Next= NewNode
End If
Current
Node
CurrentPos=1
NULL

34. Insert a Value
34
5
19
0
4
12
NULL
HeadPosition = 1
Value = 10
Algorithm InsertNode(Position, Value)
If Position < 1 Then return NULL
CurrentNode=Head
CurrentPos=1
While CurrentNode!= NULL
If CurrentPos== Position Then break
CurrentPos++
CurrentNode= CurrentNode.Next
End while
If CurrentNode== NULL Then return NULL
Create New Node NewNode
NewNode.Data= Value
If Position == 1
NewNode.Next= Head
Head = NewNode
Else
NewNode.Next= CurrentNode.Next
CurrentNode.Next= NewNode
End If
Current
Node
CurrentPos=1
10
NULL
NewNode

35. Insert a Value
35
5
19
0
4
12
NULL
HeadPosition = 1
Value = 10
Algorithm InsertNode(Position, Value)
If Position < 1 Then return NULL
CurrentNode=Head
CurrentPos=1
While CurrentNode!= NULL
If CurrentPos== Position Then break
CurrentPos++
CurrentNode= CurrentNode.Next
End while
If CurrentNode== NULL Then return NULL
Create New Node NewNode
NewNode.Data= Value
If Position == 1
NewNode.Next= Head
Head = NewNode
Else
NewNode.Next= CurrentNode.Next
CurrentNode.Next= NewNode
End If
Current
Node
CurrentPos=1
10
NULL
NewNode

36. Insert a Value
36
5
19
0
4
12
NULL
HeadPosition = 1
Value = 10
Algorithm InsertNode(Position, Value)
If Position < 1 Then return NULL
CurrentNode=Head
CurrentPos=1
While CurrentNode!= NULL
If CurrentPos== Position Then break
CurrentPos++
CurrentNode= CurrentNode.Next
End while
If CurrentNode== NULL Then return NULL
Create New Node NewNode
NewNode.Data= Value
If Position == 1
NewNode.Next= Head
Head = NewNode
Else
NewNode.Next= CurrentNode.Next
CurrentNode.Next= NewNode
End If
Current
Node
CurrentPos=1
10NewNode

37. Insert a Value
37
5
19
0
4
12
NULL
HeadPosition = 1
Value = 10
Algorithm InsertNode(Position, Value)
If Position < 1 Then return NULL
CurrentNode=Head
CurrentPos=1
While CurrentNode!= NULL
If CurrentPos== Position Then break
CurrentPos++
CurrentNode= CurrentNode.Next
End while
If CurrentNode== NULL Then return NULL
Create New Node NewNode
NewNode.Data= Value
If Position == 1
NewNode.Next= Head
Head = NewNode
Else
NewNode.Next= CurrentNode.Next
CurrentNode.Next= NewNode
End If
Current
Node
CurrentPos=1
10NewNode

38. Insert a Value
38
5
19
0
4
12
NULL
Head
Position = 1
Value = 10
Algorithm InsertNode(Position, Value)
If Position < 1 Then return NULL
CurrentNode=Head
CurrentPos=1
While CurrentNode!= NULL
If CurrentPos== Position Then break
CurrentPos++
CurrentNode= CurrentNode.Next
End while
If CurrentNode== NULL Then return NULL
Create New Node NewNode
NewNode.Data= Value
If Position == 1
NewNode.Next= Head
Head = NewNode
Else
NewNode.Next= CurrentNode.Next
CurrentNode.Next= NewNode
End If
Current
Node
CurrentPos=1
10
NewNode

39. Insert a Value
39
5
19
0
4
12
NULL
HeadPosition = 4
Value = 10
Algorithm InsertNode(Position, Value)
If Position < 1 Then return NULL
CurrentNode=Head
CurrentPos=1
While CurrentNode!= NULL
If CurrentPos== Position Then break
CurrentPos++
CurrentNode= CurrentNode.Next
End while
If CurrentNode== NULL Then return NULL
Create New Node NewNode
NewNode.Data= Value
If Position == 1
NewNode.Next= Head
Head = NewNode
Else
NewNode.Next= CurrentNode.Next
CurrentNode.Next= NewNode
End If

40. Insert a Value
40
5
19
0
4
12
NULL
HeadPosition = 4
Value = 10
Algorithm InsertNode(Position, Value)
If Position < 1 Then return NULL
CurrentNode=Head
CurrentPos=1
While CurrentNode!= NULL
If CurrentPos== Position Then break
CurrentPos++
CurrentNode= CurrentNode.Next
End while
If CurrentNode== NULL Then return NULL
Create New Node NewNode
NewNode.Data= Value
If Position == 1
NewNode.Next= Head
Head = NewNode
Else
NewNode.Next= CurrentNode.Next
CurrentNode.Next= NewNode
End If

41. Insert a Value
41
5
19
0
4
12
NULL
HeadPosition = 4
Value = 10
Algorithm InsertNode(Position, Value)
If Position < 1 Then return NULL
CurrentNode=Head
CurrentPos=1
While CurrentNode!= NULL
If CurrentPos== Position Then break
CurrentPos++
CurrentNode= CurrentNode.Next
End while
If CurrentNode== NULL Then return NULL
Create New Node NewNode
NewNode.Data= Value
If Position == 1
NewNode.Next= Head
Head = NewNode
Else
NewNode.Next= CurrentNode.Next
CurrentNode.Next= NewNode
End If
Current
Node

42. Insert a Value
42
5
19
0
4
12
NULL
HeadPosition = 4
Value = 10
Algorithm InsertNode(Position, Value)
If Position < 1 Then return NULL
CurrentNode=Head
CurrentPos=1
While CurrentNode!= NULL
If CurrentPos== Position Then break
CurrentPos++
CurrentNode= CurrentNode.Next
End while
If CurrentNode== NULL Then return NULL
Create New Node NewNode
NewNode.Data= Value
If Position == 1
NewNode.Next= Head
Head = NewNode
Else
NewNode.Next= CurrentNode.Next
CurrentNode.Next= NewNode
End If
Current
Node
CurrentPos=1

43. Insert a Value
43
5
19
0
4
12
NULL
HeadPosition = 4
Value = 10
Algorithm InsertNode(Position, Value)
If Position < 1 Then return NULL
CurrentNode=Head
CurrentPos=1
While CurrentNode!= NULL
If CurrentPos== Position Then break
CurrentPos++
CurrentNode= CurrentNode.Next
End while
If CurrentNode== NULL Then return NULL
Create New Node NewNode
NewNode.Data= Value
If Position == 1
NewNode.Next= Head
Head = NewNode
Else
NewNode.Next= CurrentNode.Next
CurrentNode.Next= NewNode
End If
Current
Node
CurrentPos=1

44. Insert a Value
44
5
19
0
4
12
NULL
HeadPosition = 4
Value = 10
Algorithm InsertNode(Position, Value)
If Position < 1 Then return NULL
CurrentNode=Head
CurrentPos=1
While CurrentNode!= NULL
If CurrentPos== Position Then break
CurrentPos++
CurrentNode= CurrentNode.Next
End while
If CurrentNode== NULL Then return NULL
Create New Node NewNode
NewNode.Data= Value
If Position == 1
NewNode.Next= Head
Head = NewNode
Else
NewNode.Next= CurrentNode.Next
CurrentNode.Next= NewNode
End If
Current
Node
CurrentPos=1

45. Insert a Value
45
5
19
0
4
12
NULL
HeadPosition = 4
Value = 10
Algorithm InsertNode(Position, Value)
If Position < 1 Then return NULL
CurrentNode=Head
CurrentPos=1
While CurrentNode!= NULL
If CurrentPos== Position Then break
CurrentPos++
CurrentNode= CurrentNode.Next
End while
If CurrentNode== NULL Then return NULL
Create New Node NewNode
NewNode.Data= Value
If Position == 1
NewNode.Next= Head
Head = NewNode
Else
NewNode.Next= CurrentNode.Next
CurrentNode.Next= NewNode
End If
Current
Node
CurrentPos=2

46. Insert a Value
46
5
19
0
4
12
NULL
HeadPosition = 4
Value = 10
Algorithm InsertNode(Position, Value)
If Position < 1 Then return NULL
CurrentNode=Head
CurrentPos=1
While CurrentNode!= NULL
If CurrentPos== Position Then break
CurrentPos++
CurrentNode= CurrentNode.Next
End while
If CurrentNode== NULL Then return NULL
Create New Node NewNode
NewNode.Data= Value
If Position == 1
NewNode.Next= Head
Head = NewNode
Else
NewNode.Next= CurrentNode.Next
CurrentNode.Next= NewNode
End If
Current
Node
CurrentPos=2

47. Insert a Value
47
5
19
0
4
12
NULL
HeadPosition = 4
Value = 10
Algorithm InsertNode(Position, Value)
If Position < 1 Then return NULL
CurrentNode=Head
CurrentPos=1
While CurrentNode!= NULL
If CurrentPos== Position Then break
CurrentPos++
CurrentNode= CurrentNode.Next
End while
If CurrentNode== NULL Then return NULL
Create New Node NewNode
NewNode.Data= Value
If Position == 1
NewNode.Next= Head
Head = NewNode
Else
NewNode.Next= CurrentNode.Next
CurrentNode.Next= NewNode
End If
Current
Node
CurrentPos=2

48. Insert a Value
48
5
19
0
4
12
NULL
HeadPosition = 4
Value = 10
Algorithm InsertNode(Position, Value)
If Position < 1 Then return NULL
CurrentNode=Head
CurrentPos=1
While CurrentNode!= NULL
If CurrentPos== Position Then break
CurrentPos++
CurrentNode= CurrentNode.Next
End while
If CurrentNode== NULL Then return NULL
Create New Node NewNode
NewNode.Data= Value
If Position == 1
NewNode.Next= Head
Head = NewNode
Else
NewNode.Next= CurrentNode.Next
CurrentNode.Next= NewNode
End If
Current
Node
CurrentPos=2

49. Insert a Value
49
5
19
0
4
12
NULL
HeadPosition = 4
Value = 10
Algorithm InsertNode(Position, Value)
If Position < 1 Then return NULL
CurrentNode=Head
CurrentPos=1
While CurrentNode!= NULL
If CurrentPos== Position Then break
CurrentPos++
CurrentNode= CurrentNode.Next
End while
If CurrentNode== NULL Then return NULL
Create New Node NewNode
NewNode.Data= Value
If Position == 1
NewNode.Next= Head
Head = NewNode
Else
NewNode.Next= CurrentNode.Next
CurrentNode.Next= NewNode
End If
Current
Node
CurrentPos=3

50. Insert a Value
50
5
19
0
4
12
NULL
HeadPosition = 4
Value = 10
Algorithm InsertNode(Position, Value)
If Position < 1 Then return NULL
CurrentNode=Head
CurrentPos=1
While CurrentNode!= NULL
If CurrentPos== Position Then break
CurrentPos++
CurrentNode= CurrentNode.Next
End while
If CurrentNode== NULL Then return NULL
Create New Node NewNode
NewNode.Data= Value
If Position == 1
NewNode.Next= Head
Head = NewNode
Else
NewNode.Next= CurrentNode.Next
CurrentNode.Next= NewNode
End If
Current
Node
CurrentPos=3

51. Insert a Value
51
5
19
0
4
12
NULL
HeadPosition = 4
Value = 10
Algorithm InsertNode(Position, Value)
If Position < 1 Then return NULL
CurrentNode=Head
CurrentPos=1
While CurrentNode!= NULL
If CurrentPos== Position Then break
CurrentPos++
CurrentNode= CurrentNode.Next
End while
If CurrentNode== NULL Then return NULL
Create New Node NewNode
NewNode.Data= Value
If Position == 1
NewNode.Next= Head
Head = NewNode
Else
NewNode.Next= CurrentNode.Next
CurrentNode.Next= NewNode
End If
Current
Node
CurrentPos=3

52. Insert a Value
52
5
19
0
4
12
NULL
HeadPosition = 4
Value = 10
Algorithm InsertNode(Position, Value)
If Position < 1 Then return NULL
CurrentNode=Head
CurrentPos=1
While CurrentNode!= NULL
If CurrentPos== Position Then break
CurrentPos++
CurrentNode= CurrentNode.Next
End while
If CurrentNode== NULL Then return NULL
Create New Node NewNode
NewNode.Data= Value
If Position == 1
NewNode.Next= Head
Head = NewNode
Else
NewNode.Next= CurrentNode.Next
CurrentNode.Next= NewNode
End If
Current
Node
CurrentPos=3

53. Insert a Value
53
5
19
0
4
12
NULL
HeadPosition = 4
Value = 10
Algorithm InsertNode(Position, Value)
If Position < 1 Then return NULL
CurrentNode=Head
CurrentPos=1
While CurrentNode!= NULL
If CurrentPos== Position Then break
CurrentPos++
CurrentNode= CurrentNode.Next
End while
If CurrentNode== NULL Then return NULL
Create New Node NewNode
NewNode.Data= Value
If Position == 1
NewNode.Next= Head
Head = NewNode
Else
NewNode.Next= CurrentNode.Next
CurrentNode.Next= NewNode
End If
Current
Node
CurrentPos=4

54. Insert a Value
54
5
19
0
4
12
NULL
HeadPosition = 4
Value = 10
Algorithm InsertNode(Position, Value)
If Position < 1 Then return NULL
CurrentNode=Head
CurrentPos=1
While CurrentNode!= NULL
If CurrentPos== Position Then break
CurrentPos++
CurrentNode= CurrentNode.Next
End while
If CurrentNode== NULL Then return NULL
Create New Node NewNode
NewNode.Data= Value
If Position == 1
NewNode.Next= Head
Head = NewNode
Else
NewNode.Next= CurrentNode.Next
CurrentNode.Next= NewNode
End If
Current
Node
CurrentPos=4

55. Insert a Value
55
5
19
0
4
12
NULL
HeadPosition = 4
Value = 10
Algorithm InsertNode(Position, Value)
If Position < 1 Then return NULL
CurrentNode=Head
CurrentPos=1
While CurrentNode!= NULL
If CurrentPos== Position Then break
CurrentPos++
CurrentNode= CurrentNode.Next
End while
If CurrentNode== NULL Then return NULL
Create New Node NewNode
NewNode.Data= Value
If Position == 1
NewNode.Next= Head
Head = NewNode
Else
NewNode.Next= CurrentNode.Next
CurrentNode.Next= NewNode
End If
Current
Node
CurrentPos=4

56. Insert a Value
56
5
19
0
4
12
NULL
HeadPosition = 4
Value = 10
Algorithm InsertNode(Position, Value)
If Position < 1 Then return NULL
CurrentNode=Head
CurrentPos=1
While CurrentNode!= NULL
If CurrentPos== Position Then break
CurrentPos++
CurrentNode= CurrentNode.Next
End while
If CurrentNode== NULL Then return NULL
Create New Node NewNode
NewNode.Data= Value
If Position == 1
NewNode.Next= Head
Head = NewNode
Else
NewNode.Next= CurrentNode.Next
CurrentNode.Next= NewNode
End If
Current
Node
CurrentPos=4

57. Insert a Value
57
5
19
0
4
12
NULL
HeadPosition = 4
Value = 10
Algorithm InsertNode(Position, Value)
If Position < 1 Then return NULL
CurrentNode=Head
CurrentPos=1
While CurrentNode!= NULL
If CurrentPos== Position Then break
CurrentPos++
CurrentNode= CurrentNode.Next
End while
If CurrentNode== NULL Then return NULL
Create New Node NewNode
NewNode.Data= Value
If Position == 1
NewNode.Next= Head
Head = NewNode
Else
NewNode.Next= CurrentNode.Next
CurrentNode.Next= NewNode
End If
CurrentPos=4
Current
Node

58. Insert a Value
58
5
19
0
4
12
NULL
HeadPosition = 4
Value = 10
Algorithm InsertNode(Position, Value)
If Position < 1 Then return NULL
CurrentNode=Head
CurrentPos=1
While CurrentNode!= NULL
If CurrentPos== Position Then break
CurrentPos++
CurrentNode= CurrentNode.Next
End while
If CurrentNode== NULL Then return NULL
Create New Node NewNode
NewNode.Data= Value
If Position == 1
NewNode.Next= Head
Head = NewNode
Else
NewNode.Next= CurrentNode.Next
CurrentNode.Next= NewNode
End If
NULL
CurrentPos=1
Current
Node
NewNode

59. Insert a Value
59
5
19
0
4
12
NULL
HeadPosition = 4
Value = 10
Algorithm InsertNode(Position, Value)
If Position < 1 Then return NULL
CurrentNode=Head
CurrentPos=1
While CurrentNode!= NULL
If CurrentPos== Position Then break
CurrentPos++
CurrentNode= CurrentNode.Next
End while
If CurrentNode== NULL Then return NULL
Create New Node NewNode
NewNode.Data= Value
If Position == 1
NewNode.Next= Head
Head = NewNode
Else
NewNode.Next= CurrentNode.Next
CurrentNode.Next= NewNode
End If
10
NULL
CurrentPos=1
Current
Node
NewNode

60. Insert a Value
60
5
19
0
4
12
NULL
HeadPosition = 4
Value = 10
Algorithm InsertNode(Position, Value)
If Position < 1 Then return NULL
CurrentNode=Head
CurrentPos=1
While CurrentNode!= NULL
If CurrentPos== Position Then break
CurrentPos++
CurrentNode= CurrentNode.Next
End while
If CurrentNode== NULL Then return NULL
Create New Node NewNode
NewNode.Data= Value
If Position == 1
NewNode.Next= Head
Head = NewNode
Else
NewNode.Next= CurrentNode.Next
CurrentNode.Next= NewNode
End If
10
NULL
CurrentPos=1
Current
Node
NewNode

61. Insert a Value
61
5
19
0
4
12
NULL
HeadPosition = 4
Value = 10
Algorithm InsertNode(Position, Value)
If Position < 1 Then return NULL
CurrentNode=Head
CurrentPos=1
While CurrentNode!= NULL
If CurrentPos== Position Then break
CurrentPos++
CurrentNode= CurrentNode.Next
End while
If CurrentNode== NULL Then return NULL
Create New Node NewNode
NewNode.Data= Value
If Position == 1
NewNode.Next= Head
Head = NewNode
Else
NewNode.Next= CurrentNode.Next
CurrentNode.Next= NewNode
End If
10
CurrentPos=1
Current
Node
NewNode

62. Insert a Value
62
5
19
0
4
12
NULL
HeadPosition = 4
Value = 10
Algorithm InsertNode(Position, Value)
If Position < 1 Then return NULL
CurrentNode=Head
CurrentPos=1
While CurrentNode!= NULL
If CurrentPos== Position Then break
CurrentPos++
CurrentNode= CurrentNode.Next
End while
If CurrentNode== NULL Then return NULL
Create New Node NewNode
NewNode.Data= Value
If Position == 1
NewNode.Next= Head
Head = NewNode
Else
NewNode.Next= CurrentNode.Next
CurrentNode.Next= NewNode
End If
10
CurrentPos=1
Current
Node
NewNode

63. Practice Question
•If any function calls InsertValue() and the insert was
successful, how will the calling function know that
the insert was successful.
•May be there is something missing.
•Can you please point out that missing statement in
the algorithm?
63

64. Searching a Value
•We have learned two searching techniques:
•Sequential Search
•Binary Search
•In linked-lists, we can only do sequential search.
•It is because, linked-list is not a random access data structure.
64

65. Searching a Value
65
Algorithm SearchNode(Head, KEY)
CurrentNode=Head
Position=1
While CurrentNode!= NULL
If CurrentNode.Data== KEY
return Position
End If
Position++
CurrentNode= CurrentNode.Next
End while
return NULL

66. Searching a Value
66
Algorithm SearchNode(Head, KEY)
CurrentNode=Head
Position=1
While CurrentNode!= NULL
If CurrentNode.Data== KEY
return Position
End If
Position++
CurrentNode= CurrentNode.Next
End while
return NULL
5 19 0 4 12 15 NULL
Head
KEY = 12

67. Searching a Value
67
Algorithm SearchNode(Head, KEY)
CurrentNode=Head
Position=1
While CurrentNode!= NULL
If CurrentNode.Data== KEY
return Position
End If
Position++
CurrentNode= CurrentNode.Next
End while
return NULL
5 19 0 4 12 15 NULL
Head
KEY = 12
CurrentNode

68. Searching a Value
68
Algorithm SearchNode(Head, KEY)
CurrentNode=Head
Position=1
While CurrentNode!= NULL
If CurrentNode.Data== KEY
return Position
End If
Position++
CurrentNode= CurrentNode.Next
End while
return NULL
5 19 0 4 12 15 NULL
Head
Position = 1
KEY = 12
CurrentNode

69. Searching a Value
69
Algorithm SearchNode(Head, KEY)
CurrentNode=Head
Position=1
While CurrentNode!= NULL
If CurrentNode.Data== KEY
return Position
End If
Position++
CurrentNode= CurrentNode.Next
End while
return NULL
5 19 0 4 12 15 NULL
Head
Position = 1
KEY = 12
CurrentNode

70. Searching a Value
70
Algorithm SearchNode(Head, KEY)
CurrentNode=Head
Position=1
While CurrentNode!= NULL
If CurrentNode.Data== KEY
return Position
End If
Position++
CurrentNode= CurrentNode.Next
End while
return NULL
5 19 0 4 12 15 NULL
Head
Position = 1
KEY = 12
CurrentNode

71. Searching a Value
71
Algorithm SearchNode(Head, KEY)
CurrentNode=Head
Position=1
While CurrentNode!= NULL
If CurrentNode.Data== KEY
return Position
End If
Position++
CurrentNode= CurrentNode.Next
End while
return NULL
5 19 0 4 12 15 NULL
Head
Position = 2
KEY = 12
CurrentNode

72. Searching a Value
72
Algorithm SearchNode(Head, KEY)
CurrentNode=Head
Position=1
While CurrentNode!= NULL
If CurrentNode.Data== KEY
return Position
End If
Position++
CurrentNode= CurrentNode.Next
End while
return NULL
5 19 0 4 12 15 NULL
Head
Position = 2
KEY = 12
CurrentNode

73. Searching a Value
73
Algorithm SearchNode(Head, KEY)
CurrentNode=Head
Position=1
While CurrentNode!= NULL
If CurrentNode.Data== KEY
return Position
End If
Position++
CurrentNode= CurrentNode.Next
End while
return NULL
5 19 0 4 12 15 NULL
Head
Position = 2
KEY = 12
CurrentNode

74. Searching a Value
74
Algorithm SearchNode(Head, KEY)
CurrentNode=Head
Position=1
While CurrentNode!= NULL
If CurrentNode.Data== KEY
return Position
End If
Position++
CurrentNode= CurrentNode.Next
End while
return NULL
5 19 0 4 12 15 NULL
Head
Position = 2
KEY = 12
CurrentNode

75. Searching a Value
75
Algorithm SearchNode(Head, KEY)
CurrentNode=Head
Position=1
While CurrentNode!= NULL
If CurrentNode.Data== KEY
return Position
End If
Position++
CurrentNode= CurrentNode.Next
End while
return NULL
5 19 0 4 12 15 NULL
Head
Position = 3
KEY = 12
CurrentNode

76. Searching a Value
76
Algorithm SearchNode(Head, KEY)
CurrentNode=Head
Position=1
While CurrentNode!= NULL
If CurrentNode.Data== KEY
return Position
End If
Position++
CurrentNode= CurrentNode.Next
End while
return NULL
5 19 0 4 12 15 NULL
Head
Position = 3
KEY = 12
CurrentNode

77. Searching a Value
77
Algorithm SearchNode(Head, KEY)
CurrentNode=Head
Position=1
While CurrentNode!= NULL
If CurrentNode.Data== KEY
return Position
End If
Position++
CurrentNode= CurrentNode.Next
End while
return NULL
5 19 0 4 12 15 NULL
Head
Position = 3
KEY = 12
CurrentNode

78. Searching a Value
78
Algorithm SearchNode(Head, KEY)
CurrentNode=Head
Position=1
While CurrentNode!= NULL
If CurrentNode.Data== KEY
return Position
End If
Position++
CurrentNode= CurrentNode.Next
End while
return NULL
5 19 0 4 12 15 NULL
Head
Position = 3
KEY = 12
CurrentNode

79. Searching a Value
79
Algorithm SearchNode(Head, KEY)
CurrentNode=Head
Position=1
While CurrentNode!= NULL
If CurrentNode.Data== KEY
return Position
End If
Position++
CurrentNode= CurrentNode.Next
End while
return NULL
5 19 0 4 12 15 NULL
Head
Position = 4
KEY = 12
CurrentNode

80. Searching a Value
80
Algorithm SearchNode(Head, KEY)
CurrentNode=Head
Position=1
While CurrentNode!= NULL
If CurrentNode.Data== KEY
return Position
End If
Position++
CurrentNode= CurrentNode.Next
End while
return NULL
5 19 0 4 12 15 NULL
Head
Position = 4
KEY = 12
CurrentNode

81. Searching a Value
81
Algorithm SearchNode(Head, KEY)
CurrentNode=Head
Position=1
While CurrentNode!= NULL
If CurrentNode.Data== KEY
return Position
End If
Position++
CurrentNode= CurrentNode.Next
End while
return NULL
5 19 0 4 12 15 NULL
Head
Position = 4
KEY = 12
CurrentNode

82. Searching a Value
82
Algorithm SearchNode(Head, KEY)
CurrentNode=Head
Position=1
While CurrentNode!= NULL
If CurrentNode.Data== KEY
return Position
End If
Position++
CurrentNode= CurrentNode.Next
End while
return NULL
5 19 0 4 12 15 NULL
Head
Position = 4
KEY = 12
CurrentNode

83. Searching a Value
83
Algorithm SearchNode(Head, KEY)
CurrentNode=Head
Position=1
While CurrentNode!= NULL
If CurrentNode.Data== KEY
return Position
End If
Position++
CurrentNode= CurrentNode.Next
End while
return NULL
5 19 0 4 12 15 NULL
Head
Position = 5
KEY = 12
CurrentNode

84. Searching a Value
84
Algorithm SearchNode(Head, KEY)
CurrentNode=Head
Position=1
While CurrentNode!= NULL
If CurrentNode.Data== KEY
return Position
End If
Position++
CurrentNode= CurrentNode.Next
End while
return NULL
5 19 0 4 12 15 NULL
Head
Position = 5
KEY = 12
CurrentNode

85. Searching a Value
85
Algorithm SearchNode(Head, KEY)
CurrentNode=Head
Position=1
While CurrentNode!= NULL
If CurrentNode.Data== KEY
return Position
End If
Position++
CurrentNode= CurrentNode.Next
End while
return NULL
5 19 0 4 12 15 NULL
Head
Position = 5
KEY = 12
CurrentNode

86. Searching a Value
86
Algorithm SearchNode(Head, KEY)
CurrentNode=Head
Position=1
While CurrentNode!= NULL
If CurrentNode.Data== KEY
return Position
End If
Position++
CurrentNode= CurrentNode.Next
End while
return NULL
5 19 0 4 12 15 NULL
Head
Position = 5
KEY = 12
CurrentNode

87. Searching a Value
87
Algorithm SearchNode(Head, KEY)
CurrentNode=Head
Position=1
While CurrentNode!= NULL
If CurrentNode.Data== KEY
return Position
End If
Position++
CurrentNode= CurrentNode.Next
End while
return NULL
5 19 0 4 12 15 NULL
Head
Position = 5
return 5
KEY = 12
CurrentNode

88. Update a Value
88
Whenever you are at a node, pointed by CurrentNode, updationis easy:
CurrentNode.Data= NewValue
5 19 0 4 12 15 NULL
Head
KEY = 12
CurrentNode

89. Update a Node’s Value
89
Algorithm UpdateNode(Head, KEY, value)
CurrentNode=Head
While CurrentNode!= NULL
If CurrentNode.Data== KEY
CurrentNode.Data= value
End while
return NULL
5 19 0 4 12 15 NULL
Head
KEY = 12
CurrentNode
value = 07

90. •What if I want to update the value of the 4
th
Node?
Algorithm UpdateNode(Head, position, value)
90
Update a Node’s Value
90
19 0 4 12 15 NULL
Head CurrentNode
5

91. Delete a Value
9191
5 19 0 4 12 15 NULL
Head
CurrentNode
Algorithm DeleteNode(Value)

92. Delete a Value
92
Algorithm DeleteNode(Value)
PrevNode= NULL
CurrentNode= Head
Position = 1
While CurrentNode!= NULL
If CurrentNode.Data== Value Then break;
Position++
PrevNode= CurrentNode
CurrentNode= CurrentNode.Next
End while
If CurrentNode= NULL Then return FALSE
If PrevNode== NULL //First element to be deleted
Head = CurrentNode.Next
Else //Middle or End Element is to be deleted
PreviousNode.Next= CurrentNode.Next
End If
Delete CurrentNode
return TRUE

93. Delete a Value
93
5
19
0
4
12
NULL
HeadValue = 5
Algorithm DeleteNode(Value)
PrevNode= NULL
CurrentNode= Head
Position = 1
While CurrentNode!= NULL
If CurrentNode.Data== Value Then break;
Position++
PrevNode= CurrentNode
CurrentNode= CurrentNode.Next
End while
If CurrentNode= NULL Then return FALSE
If PrevNode== NULL //First element to be deleted
Head = CurrentNode.Next
Else //Middle or End Element is to be deleted
PreviousNode.Next= CurrentNode.Next
End If
Delete CurrentNode
return TRUE

94. Delete a Value
94
5
19
0
4
12
NULL
HeadValue = 5
Algorithm DeleteNode(Value)
PrevNode= NULL
CurrentNode= Head
Position = 1
While CurrentNode!= NULL
If CurrentNode.Data== Value Then break;
Position++
PrevNode= CurrentNode
CurrentNode= CurrentNode.Next
End while
If CurrentNode= NULL Then return FALSE
If PrevNode== NULL //First element to be deleted
Head = CurrentNode.Next
Else //Middle or End Element is to be deleted
PreviousNode.Next= CurrentNode.Next
End If
Delete CurrentNode
return TRUE
PrevNode
NULL

95. Delete a Value
95
5
19
0
4
12
NULL
HeadValue = 5
Algorithm DeleteNode(Value)
PrevNode= NULL
CurrentNode= Head
Position = 1
While CurrentNode!= NULL
If CurrentNode.Data== Value Then break;
Position++
PrevNode= CurrentNode
CurrentNode= CurrentNode.Next
End while
If CurrentNode= NULL Then return FALSE
If PrevNode== NULL //First element to be deleted
Head = CurrentNode.Next
Else //Middle or End Element is to be deleted
PreviousNode.Next= CurrentNode.Next
End If
Delete CurrentNode
return TRUE
PrevNode
NULL
Current
Node

96. Delete a Value
96
5
19
0
4
12
NULL
HeadValue = 5
Algorithm DeleteNode(Value)
PrevNode= NULL
CurrentNode= Head
Position = 1
While CurrentNode!= NULL
If CurrentNode.Data== Value Then break;
Position++
PrevNode= CurrentNode
CurrentNode= CurrentNode.Next
End while
If CurrentNode= NULL Then return FALSE
If PrevNode== NULL //First element to be deleted
Head = CurrentNode.Next
Else //Middle or End Element is to be deleted
PreviousNode.Next= CurrentNode.Next
End If
Delete CurrentNode
return TRUE
PrevNode
NULL
Current
Node
Position=1

97. Delete a Value
97
5
19
0
4
12
NULL
HeadValue = 5
Algorithm DeleteNode(Value)
PrevNode= NULL
CurrentNode= Head
Position = 1
While CurrentNode!= NULL
If CurrentNode.Data== Value Then break;
Position++
PrevNode= CurrentNode
CurrentNode= CurrentNode.Next
End while
If CurrentNode= NULL Then return FALSE
If PrevNode== NULL //First element to be deleted
Head = CurrentNode.Next
Else //Middle or End Element is to be deleted
PreviousNode.Next= CurrentNode.Next
End If
Delete CurrentNode
return TRUE
PrevNode
NULL
Current
Node
Position=1

98. Delete a Value
98
5
19
0
4
12
NULL
HeadValue = 5
Algorithm DeleteNode(Value)
PrevNode= NULL
CurrentNode= Head
Position = 1
While CurrentNode!= NULL
If CurrentNode.Data== Value Then break;
Position++
PrevNode= CurrentNode
CurrentNode= CurrentNode.Next
End while
If CurrentNode= NULL Then return FALSE
If PrevNode== NULL //First element to be deleted
Head = CurrentNode.Next
Else //Middle or End Element is to be deleted
PreviousNode.Next= CurrentNode.Next
End If
Delete CurrentNode
return TRUE
PrevNode
NULL
Current
Node
Position=1

99. Delete a Value
99
5
19
0
4
12
NULL
HeadValue = 5
Algorithm DeleteNode(Value)
PrevNode= NULL
CurrentNode= Head
Position = 1
While CurrentNode!= NULL
If CurrentNode.Data== Value Then break;
Position++
PrevNode= CurrentNode
CurrentNode= CurrentNode.Next
End while
If CurrentNode= NULL Then return FALSE
If PrevNode== NULL //First element to be deleted
Head = CurrentNode.Next
Else //Middle or End Element is to be deleted
PreviousNode.Next= CurrentNode.Next
End If
Delete CurrentNode
return TRUE
PrevNode
NULL
Current
Node
Position=1

100. Delete a Value
100
5
19
0
4
12
NULL
HeadValue = 5
Algorithm DeleteNode(Value)
PrevNode= NULL
CurrentNode= Head
Position = 1
While CurrentNode!= NULL
If CurrentNode.Data== Value Then break;
Position++
PrevNode= CurrentNode
CurrentNode= CurrentNode.Next
End while
If CurrentNode= NULL Then return FALSE
If PrevNode== NULL //First element to be deleted
Head = CurrentNode.Next
Else //Middle or End Element is to be deleted
PreviousNode.Next= CurrentNode.Next
End If
Delete CurrentNode
return TRUE
PrevNode
NULL
Current
Node
Position=1

101. Delete a Value
101
5
19
0
4
12
NULL
Head
Value = 5
Algorithm DeleteNode(Value)
PrevNode= NULL
CurrentNode= Head
Position = 1
While CurrentNode!= NULL
If CurrentNode.Data== Value Then break;
Position++
PrevNode= CurrentNode
CurrentNode= CurrentNode.Next
End while
If CurrentNode= NULL Then return FALSE
If PrevNode== NULL //First element to be deleted
Head = CurrentNode.Next
Else //Middle or End Element is to be deleted
PreviousNode.Next= CurrentNode.Next
End If
Delete CurrentNode
return TRUE
PrevNode
NULL
Current
Node
Position=1

102. Delete a Value
102
19
0
4
12
NULL
Head
Value = 5
Algorithm DeleteNode(Value)
PrevNode= NULL
CurrentNode= Head
Position = 1
While CurrentNode!= NULL
If CurrentNode.Data== Value Then break;
Position++
PrevNode= CurrentNode
CurrentNode= CurrentNode.Next
End while
If CurrentNode= NULL Then return FALSE
If PrevNode== NULL //First element to be deleted
Head = CurrentNode.Next
Else //Middle or End Element is to be deleted
PreviousNode.Next= CurrentNode.Next
End If
Delete CurrentNode
return TRUE
PrevNode
NULL
Position=1

103. Delete a Value
103
19
0
4
12
NULL
Head
Value = 5
Algorithm DeleteNode(Value)
PrevNode= NULL
CurrentNode= Head
Position = 1
While CurrentNode!= NULL
If CurrentNode.Data== Value Then break;
Position++
PrevNode= CurrentNode
CurrentNode= CurrentNode.Next
End while
If CurrentNode= NULL Then return FALSE
If PrevNode== NULL //First element to be deleted
Head = CurrentNode.Next
Else //Middle or End Element is to be deleted
PreviousNode.Next= CurrentNode.Next
End If
Delete CurrentNode
return TRUE
PrevNode
NULL
Position=1
return True

104. Delete a Value
104
5
19
0
4
12
NULL
HeadValue = 12
Algorithm DeleteNode(Value)
PrevNode= NULL
CurrentNode= Head
Position = 1
While CurrentNode!= NULL
If CurrentNode.Data== Value Then break;
Position++
PrevNode= CurrentNode
CurrentNode= CurrentNode.Next
End while
If CurrentNode= NULL Then return FALSE
If PrevNode== NULL //First element to be deleted
Head = CurrentNode.Next
Else //Middle or End Element is to be deleted
PreviousNode.Next= CurrentNode.Next
End If
Delete CurrentNode
return TRUE

105. Delete a Value
105
5
19
0
4
12
NULL
HeadValue = 12
Algorithm DeleteNode(Value)
PrevNode= NULL
CurrentNode= Head
Position = 1
While CurrentNode!= NULL
If CurrentNode.Data== Value Then break;
Position++
PrevNode= CurrentNode
CurrentNode= CurrentNode.Next
End while
If CurrentNode= NULL Then return FALSE
If PrevNode== NULL //First element to be deleted
Head = CurrentNode.Next
Else //Middle or End Element is to be deleted
PreviousNode.Next= CurrentNode.Next
End If
Delete CurrentNode
return TRUE
PrevNode
NULL

106. Delete a Value
106
5
19
0
4
12
NULL
HeadValue = 12
Algorithm DeleteNode(Value)
PrevNode= NULL
CurrentNode= Head
Position = 1
While CurrentNode!= NULL
If CurrentNode.Data== Value Then break;
Position++
PrevNode= CurrentNode
CurrentNode= CurrentNode.Next
End while
If CurrentNode= NULL Then return FALSE
If PrevNode== NULL //First element to be deleted
Head = CurrentNode.Next
Else //Middle or End Element is to be deleted
PreviousNode.Next= CurrentNode.Next
End If
Delete CurrentNode
return TRUE
PrevNode
NULL
Current
Node

107. Delete a Value
107
5
19
0
4
12
NULL
HeadValue = 12
Algorithm DeleteNode(Value)
PrevNode= NULL
CurrentNode= Head
Position = 1
While CurrentNode!= NULL
If CurrentNode.Data== Value Then break;
Position++
PrevNode= CurrentNode
CurrentNode= CurrentNode.Next
End while
If CurrentNode= NULL Then return FALSE
If PrevNode== NULL //First element to be deleted
Head = CurrentNode.Next
Else //Middle or End Element is to be deleted
PreviousNode.Next= CurrentNode.Next
End If
Delete CurrentNode
return TRUE
PrevNode
NULL
Current
Node
Position=1

108. Delete a Value
108
5
19
0
4
12
NULL
HeadValue = 12
Algorithm DeleteNode(Value)
PrevNode= NULL
CurrentNode= Head
Position = 1
While CurrentNode!= NULL
If CurrentNode.Data== Value Then break;
Position++
PrevNode= CurrentNode
CurrentNode= CurrentNode.Next
End while
If CurrentNode= NULL Then return FALSE
If PrevNode== NULL //First element to be deleted
Head = CurrentNode.Next
Else //Middle or End Element is to be deleted
PreviousNode.Next= CurrentNode.Next
End If
Delete CurrentNode
return TRUE
PrevNode
NULL
Current
Node
Position=1

109. Delete a Value
109
5
19
0
4
12
NULL
HeadValue = 12
Algorithm DeleteNode(Value)
PrevNode= NULL
CurrentNode= Head
Position = 1
While CurrentNode!= NULL
If CurrentNode.Data== Value Then break;
Position++
PrevNode= CurrentNode
CurrentNode= CurrentNode.Next
End while
If CurrentNode= NULL Then return FALSE
If PrevNode== NULL //First element to be deleted
Head = CurrentNode.Next
Else //Middle or End Element is to be deleted
PreviousNode.Next= CurrentNode.Next
End If
Delete CurrentNode
return TRUE
PrevNode
NULL
Current
Node
Position=1

110. Delete a Value
110
5
19
0
4
12
NULL
HeadValue = 12
Algorithm DeleteNode(Value)
PrevNode= NULL
CurrentNode= Head
Position = 1
While CurrentNode!= NULL
If CurrentNode.Data== Value Then break;
Position++
PrevNode= CurrentNode
CurrentNode= CurrentNode.Next
End while
If CurrentNode= NULL Then return FALSE
If PrevNode== NULL //First element to be deleted
Head = CurrentNode.Next
Else //Middle or End Element is to be deleted
PreviousNode.Next= CurrentNode.Next
End If
Delete CurrentNode
return TRUE
PrevNode
NULL
Current
Node
Position=2

111. Delete a Value
111
5
19
0
4
12
NULL
HeadValue = 12
Algorithm DeleteNode(Value)
PrevNode= NULL
CurrentNode= Head
Position = 1
While CurrentNode!= NULL
If CurrentNode.Data== Value Then break;
Position++
PrevNode= CurrentNode
CurrentNode= CurrentNode.Next
End while
If CurrentNode= NULL Then return FALSE
If PrevNode== NULL //First element to be deleted
Head = CurrentNode.Next
Else //Middle or End Element is to be deleted
PreviousNode.Next= CurrentNode.Next
End If
Delete CurrentNode
return TRUE
PrevNode
Current
Node
Position=2

112. Delete a Value
112
5
19
0
4
12
NULL
HeadValue = 12
Algorithm DeleteNode(Value)
PrevNode= NULL
CurrentNode= Head
Position = 1
While CurrentNode!= NULL
If CurrentNode.Data== Value Then break;
Position++
PrevNode= CurrentNode
CurrentNode= CurrentNode.Next
End while
If CurrentNode= NULL Then return FALSE
If PrevNode== NULL //First element to be deleted
Head = CurrentNode.Next
Else //Middle or End Element is to be deleted
PreviousNode.Next= CurrentNode.Next
End If
Delete CurrentNode
return TRUE
PrevNode
Current
Node
Position=2

113. Delete a Value
113
5
19
0
4
12
NULL
HeadValue = 12
Algorithm DeleteNode(Value)
PrevNode= NULL
CurrentNode= Head
Position = 1
While CurrentNode!= NULL
If CurrentNode.Data== Value Then break;
Position++
PrevNode= CurrentNode
CurrentNode= CurrentNode.Next
End while
If CurrentNode= NULL Then return FALSE
If PrevNode== NULL //First element to be deleted
Head = CurrentNode.Next
Else //Middle or End Element is to be deleted
PreviousNode.Next= CurrentNode.Next
End If
Delete CurrentNode
return TRUE
PrevNode
Current
Node
Position=2

114. Delete a Value
114
5
19
0
4
12
NULL
HeadValue = 12
Algorithm DeleteNode(Value)
PrevNode= NULL
CurrentNode= Head
Position = 1
While CurrentNode!= NULL
If CurrentNode.Data== Value Then break;
Position++
PrevNode= CurrentNode
CurrentNode= CurrentNode.Next
End while
If CurrentNode= NULL Then return FALSE
If PrevNode== NULL //First element to be deleted
Head = CurrentNode.Next
Else //Middle or End Element is to be deleted
PreviousNode.Next= CurrentNode.Next
End If
Delete CurrentNode
return TRUE
PrevNode
Current
Node
Position=2

115. Delete a Value
115
5
19
0
4
12
NULL
HeadValue = 12
Algorithm DeleteNode(Value)
PrevNode= NULL
CurrentNode= Head
Position = 1
While CurrentNode!= NULL
If CurrentNode.Data== Value Then break;
Position++
PrevNode= CurrentNode
CurrentNode= CurrentNode.Next
End while
If CurrentNode= NULL Then return FALSE
If PrevNode== NULL //First element to be deleted
Head = CurrentNode.Next
Else //Middle or End Element is to be deleted
PreviousNode.Next= CurrentNode.Next
End If
Delete CurrentNode
return TRUE
PrevNode
Current
Node
Position=3

116. Delete a Value
116
5
19
0
4
12
NULL
HeadValue = 12
Algorithm DeleteNode(Value)
PrevNode= NULL
CurrentNode= Head
Position = 1
While CurrentNode!= NULL
If CurrentNode.Data== Value Then break;
Position++
PrevNode= CurrentNode
CurrentNode= CurrentNode.Next
End while
If CurrentNode= NULL Then return FALSE
If PrevNode== NULL //First element to be deleted
Head = CurrentNode.Next
Else //Middle or End Element is to be deleted
PreviousNode.Next= CurrentNode.Next
End If
Delete CurrentNode
return TRUE
PrevNode
Current
Node
Position=3

117. Delete a Value
117
5
19
0
4
12
NULL
HeadValue = 12
Algorithm DeleteNode(Value)
PrevNode= NULL
CurrentNode= Head
Position = 1
While CurrentNode!= NULL
If CurrentNode.Data== Value Then break;
Position++
PrevNode= CurrentNode
CurrentNode= CurrentNode.Next
End while
If CurrentNode= NULL Then return FALSE
If PrevNode== NULL //First element to be deleted
Head = CurrentNode.Next
Else //Middle or End Element is to be deleted
PreviousNode.Next= CurrentNode.Next
End If
Delete CurrentNode
return TRUE
PrevNode
Current
Node
Position=3

118. Delete a Value
118
5
19
0
4
12
NULL
HeadValue = 12
Algorithm DeleteNode(Value)
PrevNode= NULL
CurrentNode= Head
Position = 1
While CurrentNode!= NULL
If CurrentNode.Data== Value Then break;
Position++
PrevNode= CurrentNode
CurrentNode= CurrentNode.Next
End while
If CurrentNode= NULL Then return FALSE
If PrevNode== NULL //First element to be deleted
Head = CurrentNode.Next
Else //Middle or End Element is to be deleted
PreviousNode.Next= CurrentNode.Next
End If
Delete CurrentNode
return TRUE
PrevNode
Current
Node
Position=3

119. Delete a Value
119
5
19
0
4
12
NULL
HeadValue = 12
Algorithm DeleteNode(Value)
PrevNode= NULL
CurrentNode= Head
Position = 1
While CurrentNode!= NULL
If CurrentNode.Data== Value Then break;
Position++
PrevNode= CurrentNode
CurrentNode= CurrentNode.Next
End while
If CurrentNode= NULL Then return FALSE
If PrevNode== NULL //First element to be deleted
Head = CurrentNode.Next
Else //Middle or End Element is to be deleted
PreviousNode.Next= CurrentNode.Next
End If
Delete CurrentNode
return TRUE
PrevNode
Current
Node
Position=3

120. Delete a Value
120
5
19
0
4
12
NULL
HeadValue = 12
Algorithm DeleteNode(Value)
PrevNode= NULL
CurrentNode= Head
Position = 1
While CurrentNode!= NULL
If CurrentNode.Data== Value Then break;
Position++
PrevNode= CurrentNode
CurrentNode= CurrentNode.Next
End while
If CurrentNode= NULL Then return FALSE
If PrevNode== NULL //First element to be deleted
Head = CurrentNode.Next
Else //Middle or End Element is to be deleted
PreviousNode.Next= CurrentNode.Next
End If
Delete CurrentNode
return TRUE
PrevNode
Current
Node
Position=4

121. Delete a Value
121
5
19
0
4
12
NULL
HeadValue = 12
Algorithm DeleteNode(Value)
PrevNode= NULL
CurrentNode= Head
Position = 1
While CurrentNode!= NULL
If CurrentNode.Data== Value Then break;
Position++
PrevNode= CurrentNode
CurrentNode= CurrentNode.Next
End while
If CurrentNode= NULL Then return FALSE
If PrevNode== NULL //First element to be deleted
Head = CurrentNode.Next
Else //Middle or End Element is to be deleted
PreviousNode.Next= CurrentNode.Next
End If
Delete CurrentNode
return TRUE
PrevNode
Current
Node
Position=4

122. Delete a Value
122
5
19
0
4
12
NULL
HeadValue = 12
Algorithm DeleteNode(Value)
PrevNode= NULL
CurrentNode= Head
Position = 1
While CurrentNode!= NULL
If CurrentNode.Data== Value Then break;
Position++
PrevNode= CurrentNode
CurrentNode= CurrentNode.Next
End while
If CurrentNode= NULL Then return FALSE
If PrevNode== NULL //First element to be deleted
Head = CurrentNode.Next
Else //Middle or End Element is to be deleted
PreviousNode.Next= CurrentNode.Next
End If
Delete CurrentNode
return TRUE
PrevNode
Current
Node
Position=4

123. Delete a Value
123
5
19
0
4
12
NULL
HeadValue = 12
Algorithm DeleteNode(Value)
PrevNode= NULL
CurrentNode= Head
Position = 1
While CurrentNode!= NULL
If CurrentNode.Data== Value Then break;
Position++
PrevNode= CurrentNode
CurrentNode= CurrentNode.Next
End while
If CurrentNode= NULL Then return FALSE
If PrevNode== NULL //First element to be deleted
Head = CurrentNode.Next
Else //Middle or End Element is to be deleted
PreviousNode.Next= CurrentNode.Next
End If
Delete CurrentNode
return TRUE
PrevNode
Current
Node
Position=4

124. Delete a Value
124
5
19
0
4
12
NULL
HeadValue = 12
Algorithm DeleteNode(Value)
PrevNode= NULL
CurrentNode= Head
Position = 1
While CurrentNode!= NULL
If CurrentNode.Data== Value Then break;
Position++
PrevNode= CurrentNode
CurrentNode= CurrentNode.Next
End while
If CurrentNode= NULL Then return FALSE
If PrevNode== NULL //First element to be deleted
Head = CurrentNode.Next
Else //Middle or End Element is to be deleted
PreviousNode.Next= CurrentNode.Next
End If
Delete CurrentNode
return TRUE
PrevNode
Current
Node
Position=4

125. Delete a Value
125
5
19
0
4
12
NULL
HeadValue = 12
Algorithm DeleteNode(Value)
PrevNode= NULL
CurrentNode= Head
Position = 1
While CurrentNode!= NULL
If CurrentNode.Data== Value Then break;
Position++
PrevNode= CurrentNode
CurrentNode= CurrentNode.Next
End while
If CurrentNode= NULL Then return FALSE
If PrevNode== NULL //First element to be deleted
Head = CurrentNode.Next
Else //Middle or End Element is to be deleted
PreviousNode.Next= CurrentNode.Next
End If
Delete CurrentNode
return TRUE
PrevNode
Current
Node
Position=5

126. Delete a Value
126
5
19
0
4
12
NULL
HeadValue = 12
Algorithm DeleteNode(Value)
PrevNode= NULL
CurrentNode= Head
Position = 1
While CurrentNode!= NULL
If CurrentNode.Data== Value Then break;
Position++
PrevNode= CurrentNode
CurrentNode= CurrentNode.Next
End while
If CurrentNode= NULL Then return FALSE
If PrevNode== NULL //First element to be deleted
Head = CurrentNode.Next
Else //Middle or End Element is to be deleted
PreviousNode.Next= CurrentNode.Next
End If
Delete CurrentNode
return TRUE
PrevNode
Current
Node
Position=5

127. Delete a Value
127
5
19
0
4
12
NULL
HeadValue = 12
Algorithm DeleteNode(Value)
PrevNode= NULL
CurrentNode= Head
Position = 1
While CurrentNode!= NULL
If CurrentNode.Data== Value Then break;
Position++
PrevNode= CurrentNode
CurrentNode= CurrentNode.Next
End while
If CurrentNode= NULL Then return FALSE
If PrevNode== NULL //First element to be deleted
Head = CurrentNode.Next
Else //Middle or End Element is to be deleted
PreviousNode.Next= CurrentNode.Next
End If
Delete CurrentNode
return TRUE
PrevNode
Current
Node
Position=5

128. Delete a Value
128
5
19
0
4
12
NULL
HeadValue = 12
Algorithm DeleteNode(Value)
PrevNode= NULL
CurrentNode= Head
Position = 1
While CurrentNode!= NULL
If CurrentNode.Data== Value Then break;
Position++
PrevNode= CurrentNode
CurrentNode= CurrentNode.Next
End while
If CurrentNode= NULL Then return FALSE
If PrevNode== NULL //First element to be deleted
Head = CurrentNode.Next
Else //Middle or End Element is to be deleted
PreviousNode.Next= CurrentNode.Next
End If
Delete CurrentNode
return TRUE
PrevNode
Current
Node
Position=5

129. Delete a Value
129
5
19
0
4
12
NULL
HeadValue = 12
Algorithm DeleteNode(Value)
PrevNode= NULL
CurrentNode= Head
Position = 1
While CurrentNode!= NULL
If CurrentNode.Data== Value Then break;
Position++
PrevNode= CurrentNode
CurrentNode= CurrentNode.Next
End while
If CurrentNode= NULL Then return FALSE
If PrevNode== NULL //First element to be deleted
Head = CurrentNode.Next
Else //Middle or End Element is to be deleted
PreviousNode.Next= CurrentNode.Next
End If
Delete CurrentNode
return TRUE
PrevNode
Current
Node
Position=5

130. Delete a Value
130
5
19
0
4
12
NULL
HeadValue = 12
Algorithm DeleteNode(Value)
PrevNode= NULL
CurrentNode= Head
Position = 1
While CurrentNode!= NULL
If CurrentNode.Data== Value Then break;
Position++
PrevNode= CurrentNode
CurrentNode= CurrentNode.Next
End while
If CurrentNode= NULL Then return FALSE
If PrevNode== NULL //First element to be deleted
Head = CurrentNode.Next
Else //Middle or End Element is to be deleted
PreviousNode.Next= CurrentNode.Next
End If
Delete CurrentNode
return TRUE
PrevNode
Current
Node
Position=5

131. Delete a Value
131
5
19
0
4
12
NULL
HeadValue = 12
Algorithm DeleteNode(Value)
PrevNode= NULL
CurrentNode= Head
Position = 1
While CurrentNode!= NULL
If CurrentNode.Data== Value Then break;
Position++
PrevNode= CurrentNode
CurrentNode= CurrentNode.Next
End while
If CurrentNode= NULL Then return FALSE
If PrevNode== NULL //First element to be deleted
Head = CurrentNode.Next
Else //Middle or End Element is to be deleted
PreviousNode.Next= CurrentNode.Next
End If
Delete CurrentNode
return TRUE
PrevNode
Current
Node
Position=5

132. Delete a Value
132
5
19
0
4
12
NULL
HeadValue = 12
Algorithm DeleteNode(Value)
PrevNode= NULL
CurrentNode= Head
Position = 1
While CurrentNode!= NULL
If CurrentNode.Data== Value Then break;
Position++
PrevNode= CurrentNode
CurrentNode= CurrentNode.Next
End while
If CurrentNode= NULL Then return FALSE
If PrevNode== NULL //First element to be deleted
Head = CurrentNode.Next
Else //Middle or End Element is to be deleted
PreviousNode.Next= CurrentNode.Next
End If
Delete CurrentNode
return TRUE
PrevNode
Current
Node
Position=5

133. Delete a Value
133
5
19
0
4
NULL
HeadValue = 12
Algorithm DeleteNode(Value)
PrevNode= NULL
CurrentNode= Head
Position = 1
While CurrentNode!= NULL
If CurrentNode.Data== Value Then break;
Position++
PrevNode= CurrentNode
CurrentNode= CurrentNode.Next
End while
If CurrentNode= NULL Then return FALSE
If PrevNode== NULL //First element to be deleted
Head = CurrentNode.Next
Else //Middle or End Element is to be deleted
PreviousNode.Next= CurrentNode.Next
End If
Delete CurrentNode
return TRUE
PrevNode
Position=5

134. Delete a Value
134
5
19
0
4
NULL
HeadValue = 12
Algorithm DeleteNode(Value)
PrevNode= NULL
CurrentNode= Head
Position = 1
While CurrentNode!= NULL
If CurrentNode.Data== Value Then break;
Position++
PrevNode= CurrentNode
CurrentNode= CurrentNode.Next
End while
If CurrentNode= NULL Then return FALSE
If PrevNode== NULL //First element to be deleted
Head = CurrentNode.Next
Else //Middle or End Element is to be deleted
PreviousNode.Next= CurrentNode.Next
End If
Delete CurrentNode
return TRUE
PrevNode
Position=5
return True

135. Advantages of Linked List
•Linked list is a dynamic data structure so it can grow and shrink at
runtime by allocating and deallocating memory. So there is no need
to give initial size of linked list.
•Insertion and deletion of nodes are really easier. Unlike array here we
don’t have to shift elements after insertion or deletion of an element.
In linked list we just have to update the address present in next
pointer of a node.
135

136. Advantages of Linked List
•As size of linked list can increase or decrease at run time so there is
no memory wastage. In case of array there is lot of memory wastage,
like if we declare an array of size 10 and store only 6 elements in it
then space of 4 elements are wasted. There is no such problem in
linked list as memory is allocated only when required.
136

137. Disadvantages of Linked List
•More memory is required to store elements in linked list as compared
to array. Because in linked list each node contains a pointer and it
requires extra memory for itself.
•Elements or nodes traversal is difficult in linked list. We can not
randomly access any element as we do in array by index. For example
if we want to access a node at position n then we have to traverse all
the nodes before it. So, time required to access a node is large.
137

138. Disadvantages of Linked List
•In linked list reverse traversing is really difficult. In case ofdoubly
linked listits easier but extra memory is required for back pointer
hence wastage of memory.
138

139. Cost of Operations
139
AccessSearch InsertionDeletion
Array O(1) O(n) O(n) O(n)
Singly Linked ListO(n) O(n) O(1) O(1)
Doubly Linked ListO(n) O(n) O(1) O(1)

140. Practice Question
•Suppose, we want a linked list such that whenever we
insert a value, it is inserted in a position such that it is
greater than or equal to the value of previous node
but less than the value of the next node. Such a
linked-list is called an Ordered Linked List. Write an
algorithm for its insert procedure.
140

141. DATA STRUCTURES AND
ALGORITHMS
Doubly Linked Lists
141

142. Doubly Linked List
•Doubly Linked List is a variation of Linked list in which navigation is
possible in both ways, either forward and backward easily as
compared to Single Linked List.
142

143. Operations on Doubly Linked List
1.Searching/Traversing
2.Updation
3.Inserting
1.In empty list
2.In front of list
3.In the middle of list
4.At the end
4.Deleting
1.First Node
2.Middle node
3.Last node
143

144. Node data
•info: the user's data
•next, back: the address of the next and
previous node in the list
.back .next.info

145. Doubly Linked Lists
•In a Doubly Linked List each item points to both its
predecessor and successor
•prevpoints to the predecessor
•nextpoints to the successor
10 7020 5540
Head
Cur
Cur->nextCur->prev

146. Node data (cont.)
template<class ItemType>
struct NodeType {
ItemType info;
NodeType<ItemType>* next;
NodeType<ItemType>* back;
};

147. Finding a List Item
•We no longer need to use prevLocation(we can
get the predecessor of a node using its back
member)

148. Finding a List Item (cont.)

149. FindItem(listData, item, location, found)
•RetrieveItem, InsertItem, and DeleteItemall require a search !
•Write a general non-member function SearchItemthat takes item as a
parameter and returns locationand found.
•InsertItemand DeleteItemneed location(ignore found)
•RetrieveItemneeds found (ignores location)

150. b

151. Finding a List Item (cont.)
template<class ItemType>
void FindItem(NodeType<ItemType>* listData, ItemType item,
NodeType<ItemType>* &location, bool &found)
{
// precondition: list is not empty
bool moreToSearch = true;
location = listData;
found = false;
while( moreToSearch && !found) {
if(item < location->info)
moreToSearch = false;
else if(item == location->info)
found = true;
else {
if(location->next == NULL)
moreToSearch = false;
else
location = location->next;
}
}
}

152. Inserting into a Doubly Linked List
1. newNode->back = location->back; 3. location->back->next=newNode;
2. newNode->next = location 4. location->back = newNode;

153. Inserting a Node
•Insert a node Newbefore Cur(not at front or rear)
10 7020 55
40Head
New
Cur
New->next = Cur;
New->prev = Cur->prev;
Cur->prev = New;
(New->prev)->next = New;

154. Special case: inserting in the beginning

155. Inserting into a Doubly Linked List
template<class ItemType>
void SortedType<ItemType>::InsertItem(ItemType item)
{
NodeType<ItemType>* newNode;
NodeType<ItemType>* location;
bool found;
newNode = new NodeType<ItemType>;
newNode->info = item;
if (listData != NULL) {
FindItem(listData, item, location, found);
if (location->info > item) {
newNode->back = location->back;
newNode->next = location;
if (location != listData) // special case
(location->back)->next = newNode;
else
listData = newNode;
location->back = newNode;
}
(1)
(2)
(3)
(4)
(3)

156. Inserting into a Doubly Linked List
(cont.)
else { // insert at the end
newNode->back = location;
location->next = newNode;
newNode->next = NULL;
}
}
else { // insert into an empty list
listData = newNode;
newNode->next = NULL;
newNode->back = NULL;
}
length++;
}

157. Deleting from a Doubly Linked List
•Be careful about the end cases!!

158. Deleting a Node
•Delete a node Cur(not at front or rear)
(Cur->prev)->next = Cur->next;
(Cur->next)->prev = Cur->prev;
delete Cur;
10 7020 5540
Head
Cur

159. Doubly Linked List Operations
*insertNode(NodePtr Head, int item)
//add new node to ordered doubly linked list
*deleteNode(NodePtr Head, int item)
//remove a node from doubly linked list
*searchNode(NodePtr Head, int item)
*print(NodePtr Head, int item)

160. NodePtr searchNode(NodePtr Head, int item){
NodePtr Cur = Head->next;
while(Cur != Head){
if(Cur->data == item)
return Cur;
if(Cur->data < item)
Cur = Cur->next;
else
break;
}
return NULL;
}
Searching a node:

161. void print(NodePtrHead){
NodePtrCur=Head->next;
while(Cur != Head){
cout<< Cur->data << " ";
Cur = Cur->next;
}
cout<< endl;
}
Print the whole circular list:

162. Circular Linked List
•Circular Linked List is a variation of Linked list in which the first
element points to the last element and the last element points to the
first element.
•Both Singly Linked List and Doubly Linked List can be made into a
circular linked list.
•In doubly linked list, the next pointer of the last node points to the
first node and the previous pointer of the first node points to the last
node making the circular in both directions.
162

163. Operations on Circular Linked List
1.Searching/Traversing
2.Updation
3.Inserting
1.In empty list
2.In front of list
3.In the middle of list
4.At the end
4.Deleting
1.First Node
2.Middle node
3.Last node
163

164. Operations on Circular Linked List
1.Searching/Traversing
2.Updation
3.Inserting
1.In empty list
2.In front of list
3.In the middle of list
4.At the end
4.Deleting
1.First Node
2.Middle node
3.Last node
164

165. Advantages of Linked List
•Linked list is a dynamic data structure so it can grow and shrink at
runtime by allocating and deallocating memory. So there is no need
to give initial size of linked list.
•Insertion and deletion of nodes are really easier. Unlike array here we
don’t have to shift elements after insertion or deletion of an element.
In linked list we just have to update the address present in next
pointer of a node.
165

166. Advantages of Linked List
•As size of linked list can increase or decrease at run time so there is
no memory wastage. In case of array there is lot of memory wastage,
like if we declare an array of size 10 and store only 6 elements in it
then space of 4 elements are wasted. There is no such problem in
linked list as memory is allocated only when required.
166

167. Disadvantages of Linked List
•More memory is required to store elements in linked list as compared
to array. Because in linked list each node contains a pointer and it
requires extra memory for itself.
•Elements or nodes traversal is difficult in linked list. We can not
randomly access any element as we do in array by index. For example
if we want to access a node at position n then we have to traverse all
the nodes before it. So, time required to access a node is large.
167

168. Disadvantages of Linked List
•In linked list reverse traversing is really difficult. In case ofdoubly
linked listits easier but extra memory is required for back pointer
hence wastage of memory.
168

169. Practice Question
•Suppose, we want a linked list such that whenever we
insert a value, it is inserted in a position such that it is
greater than or equal to the value of previous node
but less than the value of the next node. Such a
linked-list is called an Ordered Linked List. Write an
algorithm for its insert procedure.
169

170. Cost of Operations
170