DATA STRUCUTERE
CHAPTER FIVE
INTRODUCTION TO DATA
STRUCTURE
Lecture 5
Link list
2
Link list is liner collection of special designed
data element, called nodes linked to one
another by means of pointer. Each node is
divided into two parts: the first part contains
the information of the element and second part
contains the address of next node in the lined
list.
Linked
Linked List is used extensively in Computer Science
applications, for example, in maintaining databases,
operating system etc.
Slide 1- 3
Linked List
Insertion and deletion are easier and efficient.
Linked list provides flexibility in inserting a data
item at a specified position and deletion of a data
item from the given position.
Many complex applications can be easily carried
out with linked list.
Slide 1- 4
ADVANTAGES AND
DISADVANTAGES
5
Linked list have many advantages and some of them
are:
1. Linked list are dynamic data structure. That is,
they can grow or shrink during the execution of
a program.
2. Insertion and deletion are easier and efficient.
Linked list provides flexibility in inserting a
data item at a specified position and deletion of
a data item from the given position.
ADVANTAGES AND DISADVANTAGES
3. You can perform operations like insertion and
deletion with ease
4. It is a dynamic data structure, i.e., it does not have a
fixed size
5. It doesn’t require the movement of nodes for
insertion and deletion
6. It doesn’t need elements to be stored in consecutive
memory spaces
7. It does not waste space as it uses space according to
the requirement
Cont..
7
Linked list has following disadvantages
1. More memory: to store an integer number, a node with
integer data and address field is allocated.
2. That is more memory space is needed.
3. It requires more storage space because it also stores the
next pointer with data
4. If you have to reach any node, then you have to go
through every node before it
5. You can not traverse it from anywhere but the head
node
Cont
6. It requires a different amount of time to access
any elements
7. Sorting is complex in this linked list
Operation On Linked List
The primitive operations performed on the
linked list are as follows
1. Creation
2. Insertion
3. Deletion
4. Traversing
Slide 1- 9
10
Cont..
Creation operation is used to create a linked list. Once a
linked list is created with one node, insertion operation
can be used to add more elements in a node.
Insertion operation is used to insert a new node at any
specified location in the linked list.
A new node may be inserted.
(a) At the beginning of the linked list
(b) At the end of the linked list
(c) At any specified position in between in a linked list
Cont..
11
Deletion operation is used to delete an item (or
node) from the linked list. A node
may be deleted from the
(a) Beginning of a linked list
(b) End of a linked list
(c) Specified location of the linked list
Cont..
12
Traversing is the process of going through all the
nodes from one end to another end of a linked list.
In a singly linked list we can visit from left to right,
forward traversing, nodes only. But in doubly
linked list forward and backward traversing is
possible.
Types Of Linked List
Basically we can divide the linked list into the
following three types in the order in which they (or
node) are arranged.
1. Singly linked list
2. Doubly linked list
3. Circular linked list
Slide 1- 13
Singly Linked Lists
What is a singly-linked list?
Why linked lists?
Singly-linked lists vs. 1D-arrays
Creation node
Traversal
Insertion after and before an element
Deletion
What is a Singly-linked list?
A singly linked list is a dynamic data structure
consisting of a sequence of nodes, forming a linear
ordering.
Each node stores:
Element (data object)
Node:
Reference (i.e., address) to the next node
Singly-linked list:
Single Linked list
A singly linked list is collection of nodes where each node
contains address of next node in order to keep track of nodes
in the linked lists. A node is nothing but collection of data and
link fields.
All the nodes in a singly linked list are arranged sequentially
by linking with a pointer. A singly linked list can grow or
shrink, because it is a dynamic data structure. Following
figure explains the different operations on a singly linked list.
Data Link
NODE
Single Linked list
start
10 30 40
start
Fig. 5.6. Insert a node with DATA(40) at the end
30
Fig. 5.5. Create a node with DATA(30)
start
30 40
Fig. 5.6. Insert a node with DATA(40) at the end
Slide 1- 17
Single Linked list
There can be any number of data field but there will be
only on link field to each node
DATA 1 DATA 2 ………. Link
NODE
The link field contains address of next node and data
field contains actual data of the node
Slide 1- 18
Why linked lists?
Linked lists are used to implement many important data structures such
as stacks, queues, graphs, hash tables, etc.
Linked lists are used as components of some data structures.
Examples: trees, skip lists, etc.
LISP An important programming language in artificial intelligence
makes extensive use of linked lists in performing symbolic processing.
Memory management: An important role of operating systems. An
operating system must decide how to allocate and reclaim storage for
processes running on the system. A linked list can be used to keep
track of portions of memory that are available for allocation.
Scrolled lists, components found in graphical user interfaces, can be
implemented using linked lists.
Singly-linked lists vs. 1D-arrays
ID-array Singly-linked list
Fixed size: Resizing is expensive Dynamic size
Insertions and Deletions are inefficient: Insertions and Deletions are efficient: No
Elements are usually shifted shifting
Random access i.e., efficient indexing No random access
Not suitable for operations requiring
accessing elements by index such as sorting
No memory waste if the array is full or almost Extra storage needed for references; however
full; otherwise may result in much memory uses exactly as much memory as it needs
waste.
Sequential access is faster because of greater Sequential access is slow because of low
locality of references [Reason: Elements in locality of references [Reason: Elements not in
contiguous memory locations] contiguous memory locations]
Example
#include <iostream>
using namespace std;
class node
{ public:
int data;
node* next;};
void println(node* n)
{while(n!=NULL)
{ cout<<n->data <<" ";
n=n->next; } }
int main() head->data=1;
{ head-
node* head=NULL; >next=second;
node* second=NULL; second->data=2;
node* third=NULL; second-
>next=third;
node* four=NULL;
third->data=3;
third->next=four;
head=new node();
four->data=4;
second=new node();
four->next=NULL;
third=new node();
println(head);
four=new node();
return 0; }
#include <iostream> void insertAfter(Node*
using namespace std; prev_node, int new_data)
class Node { if (prev_node == NULL)
{ public: { cout<<"the given
int data; previous node cannot be
Node *next; }; NULL";
void push(Node** head_ref, return; }
int new_data) Node* new_node = new
{ Node* new_node = new Node();
Node(); new_node->data =
new_node->data = new_data;
new_data;
new_node->next =
new_node->next =
prev_node->next;
(*head_ref);
prev_node->next =
(*head_ref) =
new_node; }
new_node; }
void append(Node** head_ref, int void printList(Node *node)
new_data)
{ while (node != NULL)
{ Node* new_node = new { cout<<" "<<node-
Node();
>data;
Node *last = *head_ref;
node = node->next; } }
new_node->data = new_data; int main()
new_node->next = NULL; { Node* head = NULL;
if (*head_ref == NULL) append(&head, 6);
{ *head_ref = push(&head, 7);
new_node; push(&head, 1);
return; } append(&head, 4);
while (last->next != NULL) insertAfter(head->next,
8);
last = last->next;
cout<<"Created Linked
last->next = new_node; list is: ";
return; } printList(head);
return 0; }
Example
#include <bits/stdc++.h> Node *prev = head;
using namespace std; while(prev->next !=
class Node NULL && prev->next !=
{ public: n)
int data; prev = prev->next;
Node *next; };
if(prev->next ==
void deleteNode(Node *head, Node *n) NULL)
{ if(head == n)
{ cout << "\
{ if(head->next == NULL)
nGiven node is not
{ cout << "There is only one node."
present in Linked
<< " The list can't be made empty ";
List";
return; }
head->data = head->next->data;
return; }
n = head->next; prev->next = prev-
head->next = head->next->next; >next->next;
free(n); free(n);
return; } return; }
void push(Node void printList(Node *head)
**head_ref, int {
new_data) while(head!=NULL)
{ Node *new_node {
= new Node(); cout<<head-
new_node->data = >data<<" ";
new_data; head=head-
>next;
new_node->next =
*head_ref;
}
cout<<endl;
*head_ref =
new_node; }
}
int main() cout<<"Given Linked List: ";
{ Node *head = NULL; printList(head);
push(&head,3); cout<<"\nDeleting node "<< head-
>next->next->data<<" ";
push(&head,2); deleteNode(head, head->next->next);
push(&head,6); cout<<"\nModified Linked List: ";
push(&head,5); printList(head);
push(&head,11); cout<<"\nDeleting first node ";
push(&head,10); deleteNode(head, head);
cout<<"\nModified Linked List: ";
push(&head,15);
printList(head);
push(&head,12); return 0; }
END
?
