Lecture Notes Data Structures and Algorithms
Linked List
Contents
Linked List
Memory Representation
Operations on Linked List
Traversing
Searching
Insertion
o Node Insertion At Start
o Node Insertion At End
o Node Insertion after a specified location
Deletion
o Deletion of first node
o Deletion of last Node
o Deletion of a specified Node
Count number of Node
Insert a new Node as tenth Node
Delete tenth Node
Advantages of Link list
Disadvantages of Link list
Linked List
This is most widely used data structure and also very much practical one. Here the elements
(nodes) are kept in disjoint memory locations. Each node consists of two parts one for the data
and other for address of next node. In array approach which is hardly used but just to clarify the
concept. One might be kept for data portion and second for maintaining the appropriate address
to next node. As shown in figure below.
1/13
Lecture Notes Data Structures and Algorithms
1 W 5
2 S 3
3 I 4
4 F NULL
5 A 2
But this does not reveal the actual meaning of linked list so we go for a pointer approach. Let
us consider the operations of insertion and deletion in a sequentially allocated list. Assume that
we have an n-element list and that it is required to insert a new element between the second and
the third elements. In this case, the last n – 2 elements of the list must be physically moved to
make room for the new element. For large-sized lists, which are subjected to many insertions,
this insertion approach can be very costly. The same conclusion holds in the case of deletion,
since all elements after the deleted element must be moved up so as to use the vacated space
caused by the deletion.
These two allocation methods (linked and sequential) can be compared with respect to
other operations as well. For a search operation in a linked list, we must follow the link from the
first node onwards until the desired node is found. This operation is certainly inferior to the
computed-address method of locating an element in a sequentially allocated list. If we want to
split or join two linked lists, then these operations involve the changing of pointer fields without
having to move any nodes. Such is not the case for sequentially allocated counterparts.
Clearly, pointers or links consume additional memory. The cost of this additional memory
becomes less important as the information contents of a node require more memory. In the above
discussion the actual address of a node was used in the link field for illustration purposes. In
practice, however, this address may be of no concern (and indeed unknown) to the programmer.
Therefore, in the remainder of our discussion of linked structure, the arrow symbol is used
exclusively to denote a successor node.
The use of pointers is only to specify the relationship of logical adjacency among
elements of a linear list. This is an important point to emphasize – the notion of logical adjacency
versus physical adjacency. In vector (or sequential) storage, they are the same. In linked storage,
they are not. Therefore, we have more flexibility with linked storage.
2/13
Lecture Notes Data Structures and Algorithms
Memory Representation
A linked list provides a more flexible storage system in that it doesn’t use array at all.
Instead, space for each data item is obtained as needed with new, and each item is connected or
linked, to the next data item using a pointer. The individual item don’t need to be located in the
memory contiguously, the way arrays are; they can be scattered anywhere.
struct link { // node of list
int data; //data item
link* next; //pointer to next link
};
// class of Linked List
class linklist { //a linked list
private:
link* first; //pointer to first link
public:
linklist() //no-argument constructor
{ first = NULL; } //no first link
};
Operations on Linked List
Following are the major operations on linked lists.
1. Traversing
Following C++ code is used to traverse a linked list.
void linklist::traverse() { //display all links
link* current = first; //set ptr to first link
while( current != NULL ) { //quit on last link
cout << current->data << endl; //print data
current = current->next; //move to next link
}
}
3/13
Lecture Notes Data Structures and Algorithms
2. Searching
Following C++ code is used to traverse a linked list.
void linklist::search(int d) { //display all links
if (first == NULL) {
cout << “List is empty”;
return;
}
int loc=0;
link* current = first; //set ptr to first link
while( current != NULL ) { //quit on last link
if (current->data == d) {
cout << “Item found” << endl;
loc=1;
}
current = current->next;
}
if (loc == 0)
cout << “Item not found”;
}
3. Insertion
A new node can be inserted in the following ways.
3.1 Node Insertion At Start
Following code inserts a new node at the start of linked list.
void linklist::InsertAtStart(int d) { //add data item
link* newlink = new link; //make a new link
newlink->data = d; //give it data
newlink->next = first;
first = newlink;
}
The given C++ program executes insertion at start.
int main() {
linklist li; //make linked list
[Link](25); //add four items to list
li. InsertAtStart (36);
li. InsertAtStart (49);
[Link]();
}
4/13
Lecture Notes Data Structures and Algorithms
Insertion at start
25 NULL
(Head)
36 &25 25 NULL
49 &36 36 &25 25 NULL
49 NUL 36 &25 25 NULL
Deletion at start
(Head)
3.2 Node Insertion At End
This approach is simpler it is used for insertion at end.
void linklist::InsertAtEnd(int d) { //add data item
link* newlink = new link; //make a new link
newlink->data = d; //give it data
newlink->next = NULL;
if (first == NULL) {
first = newlink;
}
else {
link *current = first;
while (current->next != NULL)
current = current->next;
current->next = newlink; //now first points to this
}
}
5/13
Lecture Notes Data Structures and Algorithms
3.3 Node Insertion after a specified location
Following C++ code is used to insert new node after a specified node of a linked list.
void linklist::InsertAtLoc(int n, int d) { //display all links
if (first == NULL) {
cout << “List is empty”;
return;
}
int loc=0;
link* current = first; //set ptr to first link
while( current != NULL ) { //quit on last link
if (current->data == d) {
link* newlink = new link;
newlink->data = n;
newlink->next = current->next;
current->next = newlink;
loc=1;
}
current = current->next;
}
if (loc == 0)
cout << “Item not found”;
}
4. Deletion
A new node can be deleted in the following ways.
4.1 Deletion of first node
Following code deletes a node at the start of linked list.
6/13
Lecture Notes Data Structures and Algorithms
void linklist::DeleteAtStart() { //add data item
if (first == NULL) {
cout << “Unable to delete List is empty”;
return;
}
link* temp = first; //save first in a new link
first = first->next;
temp->next = NULL;
delete temp;
}
4.2 Deletion of last Node
Following code deletes a node at the end of linked list.
void linklist::DeleteAtEnd() { //add data item
if (first == NULL) {
cout << “Unable to delete List is empty”;
return;
}
else { // for more than 1 nodes existing in a list
link* temp=NULL, *current=first;
while (current->next !=NULL) {
temp=current;
current = current->next;
}
temp->next = NULL;
delete current;
}
}
4.3 Deletion of a specified Node
Following C++ code is used to delete a specified node in a linked list.
void linklist::DeleteAtLoc(int d) { //display all links
if (first == NULL) {
cout << “Unable to delete List is empty”;
return;
}
7/13
Lecture Notes Data Structures and Algorithms
int loc=0;
link* temp=NULL, *current=first;
while( current != NULL ) { //quit on last link
if (current->data == d) {
if (current == first) { // if desired data is on first node
Link *t = first;
first = first->next;
t->next =NULL;
delete t;
current = first;
loc=1;
continue;
} else { // if desired data is on any other node
temp->next = current->next;
current->next = NULL;
delete current;
current =temp->next;
loc=1;
}
}
temp=current;
current = current->next;
}
if (loc == 0)
cout << “Item not found”;
}
5. Count number of Node
Following C++ code is used to count the number of nodes in a linked list.
void linklist::CountNodes() { //display all links
link* current = first; //set ptr to first link
int n=0;
while( current != NULL ) { //quit on last link
n++;
current = current->next; //move to next link
}
cout << “Number of nodes = ” << n;
}
6. Insert a new Node as tenth Node
Following C++ code is used to insert a new node as tenth node in a linked list.
8/13
Lecture Notes Data Structures and Algorithms
void linklist::Insert10thNodes(int n) {
if (first == NULL) {
cout << “List is empty”;
return;
}
link* current = first; //set ptr to first link
int n=0;
while( current != NULL ) { //quit on last link
n++;
if (n == 9) {
link* newlink = new link;
newlink->data = n;
newlink->next = current->next;
current->next = newlink;
break;
}
current = current->next; //move to next link
}
}
7. Delete tenth Node
Following C++ code is used to delete tenth node in a linked list.
void linklist::Delete10thNodes() { //display all links
if (first == NULL) {
cout << “List is empty”;
return;
}
link* current = first *temp=NULL; //set ptr to first link
int n=0;
while( current != NULL ) { //quit on last link
n++;
if (n == 10) {
temp->next = current->next;
current->next = NULL;
delete current;
break;
}
temp = current;
current = current->next; //move to next link
}
}
9/13
Lecture Notes Data Structures and Algorithms
Advantages of Link list
Following are the major advantages of link list.
No contiguous memory is required.
No wastage of memory
Efficient insertion and deletion of data elements
Disadvantages of Link list
Following are the major disadvantages of link list.
It is not easy to access an element directly.
It is not efficient in searching and sorting
10/13
Lecture Notes Data Structures and Algorithms
Practice Problems
Question 1
11/13
Lecture Notes Data Structures and Algorithms
Question 2
12/13
Lecture Notes Data Structures and Algorithms
13/13