Data Structure Dynamically handling #3
In this article, we will explore the
topics for better understanding.
1. Dynamic Data Structure
2. Representation of
Dynamic Data in Pictorial form
3. Basic Operations
4. Details and Code of the
operations
A linked list is a sequence of data structures,
which are connected together via links.
A Linked List is a sequence of links containing items. Each link contains a connection to another link. Linked lists are the second most-used data structure after arrays. The following are the important terms to understand the concept of Linked Lists.
·
Link − Each link of a linked list can store data called an element.
·
Next − Each link of a linked list contains a
link to the next link called Next.
·
LinkedList − A Linked List contains the connection
link to the first link called First.
Linked List Representation
As per the above illustration, following are the
important points to be considered.
·
Linked List contains a
link element called first.
·
Each link carries a data
field(s) and a link field called next.
·
Each link is linked with
its next link using its next link.
·
Last link carries a link
as null to mark the end of the list.
Types of Linked Lists
Following are the various types of linked list.
·
Simple
Linked List − Item navigation
is forward only.
·
Doubly
Linked List − Items can be
navigated forward and backward.
·
Circular
Linked List − The last item
contains link of the first element as next and the first element has a link to
the last element as the previous.
Basic Operations
Following are the basic operations supported by
a list.
·
Insertion − Adds an element at the beginning of the
list.
·
Deletion − Deletes an element at the beginning of
the list.
·
Display − Displays the complete list.
·
Search − Searches an element using the given key.
·
Delete − Deletes an element using the given key.
Insertion Operation
Adding a new node in the linked list is a more than
one-step activity. We shall learn this with diagrams here. First, create a node
using the same structure and find the location where it has to be inserted.
Imagine that we are inserting a node B (NewNode),
between A (LeftNode) and C (RightNode). Then
point B.next to C −
NewNode.next
−> RightNode;
It should look like this −
Now, the next node at the left should point to the new node.
LeftNode.next
−> NewNode;
This will put the new node in the middle of the
two. The new list should look like this −
Deletion Operation
Deletion is also a more than one-step process.
We shall learn with pictorial representation. First, locate the target node to
be removed, by using searching algorithms.
The left (previous) node of the target node now
should point to the next node of the target node −
LeftNode.next
−> TargetNode.next;
This will remove the link that was pointing to
the target node. Now, using the following code, we will remove what the target
node is pointing at.
TargetNode.next
−> NULL;
We need to use the deleted node. We can keep
that in memory otherwise we can simply deallocate memory and wipe off the
target node completely.
This operation is a thorough one. We need to make the last node to be pointed by the head node and reverse the whole linked list.
First, we traverse to the end of the list. It should be pointing to NULL. Now, we shall make it point to its previous node −
We have to make sure that the last node is not the last node. So we'll have some temp node, which looks like the head node pointing to the last node. Now, we shall make all left side nodes point to their previous nodes one by one.
Except for the node (first node) pointed by the head
node, all nodes should point to their predecessor, making them their new
successor. The first node will point to NULL.
We'll make the head node point to the new first
node by using the temp node.
A doubly Linked List is a variation of a Linked list in which navigation is possible in both ways, either forward and backward easily as compared to a Single Linked List. The following are the important terms to understand the concept of a doubly linked list.
·
Link − Each link of a linked list can store data called an element.
·
Next − Each link of a linked list contains a
link to the next link called Next.
·
Prev − Each link of a linked list contains a
link to the previous link called Prev.
·
LinkedList − A Linked List contains the connection
link to the first link called First and to the last link called Last.
Doubly Linked List Representation
As per the above illustration, the following are the
important points to be considered.
·
Doubly Linked List
contains a link element called first and last.
·
Each link carries a data
field(s) and two link fields called next and prev.
·
Each link is linked with
its next link using its next link.
·
Each link is linked with
its previous link using its previous link.
·
The last link carries a
link as null to mark the end of the list.
Basic Operations
Following are the basic operations supported by
a list.
·
Insertion − Adds an element at the beginning of the
list.
·
Deletion − Deletes an element at the beginning of
the list.
·
Insert
Last − Adds an element
at the end of the list.
·
Delete
Last − Deletes an
element from the end of the list.
·
Insert
After − Adds an element
after an item of the list.
·
Delete − Deletes an element from the list using
the key.
·
Display
forward − Displays the
complete list in a forward manner.
·
Display
backward − Displays the
complete list in a backward manner.
Insertion Operation
Following code demonstrates the insertion
operation at the beginning of a doubly linked list.
Example
//insert link at the first location
void insertFirst(int key, int data) {
//create a link
struct node *link =
(struct node*) malloc(sizeof(struct node));
link->key = key;
link->data =
data;
if(isEmpty()) {
//make it the
last link
last = link;
} else {
//update first
prev link
head->prev =
link;
}
//point it to old
first link
link->next =
head;
//point first to
new first link
head = link;
}
========
Deletion Operation
Following code demonstrates the deletion
operation at the beginning of a doubly linked list.
Example
//delete first item
struct node* deleteFirst() {
//save reference to
first link
struct node
*tempLink = head;
//if only one link
if(head->next ==
NULL) {
last = NULL;
} else {
head->next->prev = NULL;
}
head =
head->next;
//return the
deleted link
return tempLink;
}
========
Insertion at the End of an Operation
Following code demonstrates the insertion
operation at the last position of a doubly linked list.
Example
//insert link at the last location
void insertLast(int key, int data) {
//create a link
struct node *link =
(struct node*) malloc(sizeof(struct node));
link->key = key;
link->data =
data;
if(isEmpty()) {
//make it the
last link
last = link;
} else {
//make link a
new last link
last->next =
link;
//mark old last
node as prev of new link
link->prev =
last;
}
//point last to new
last node
last = link;
}
=========
Simple (Single Linked List)
Reverse Display
#include <stdio.h>
#include <stdlib.h>
struct node {
int data;
struct node *next;
};
struct node *head = NULL;
struct node *current = NULL;
//display the list
void printList() {
struct node *ptr =
head;
printf("\n[head] =>");
//start from the
beginning
while(ptr != NULL)
{
printf(" %d
=>",ptr->data);
ptr =
ptr->next;
}
printf("
[null]\n");
}
//insert link at the first location
void insert(int data) {
//create a link
struct node *link =
(struct node*) malloc(sizeof(struct node));
//link->key =
key;
link->data =
data;
//point it to old
first node
link->next =
head;
//point first to
new first node
head = link;
}
int main() {
insert(10);
insert(20);
insert(30);
insert(1);
insert(40);
insert(56);
printList();
return 0;
}
============
Output
Output of the program should be −
[head] => 56 => 40 => 1 => 30 => 20 => 10 => [null]
***
Removal of Linked List
#include <stdio.h>
#include <stdlib.h>
struct node {
int data;
struct node *next;
};
struct node *head = NULL;
struct node *current = NULL;
struct node *prev = NULL;
//Create Linked List
void insert(int data) {
// Allocate memory
for new node;
struct node *link =
(struct node*) malloc(sizeof(struct node));
link->data =
data;
link->next =
NULL;
// If head is
empty, create new list
if(head==NULL) {
head = link;
return;
}
current = head;
// move to the end
of the list
while(current->next!=NULL)
current =
current->next;
// Insert link at
the end of the list
current->next =
link;
}
void display() {
struct node *ptr =
head;
printf("head]
=>");
//start from the
beginning
while(ptr != NULL)
{
printf(" %d
=>",ptr->data);
ptr =
ptr->next;
}
printf("
[null]\n");
}
void remove_data(int data) {
int pos = 0;
if(head==NULL) {
printf("Linked List not initialized");
return;
}
if(head->data ==
data) {
if(head->next
!= NULL) {
head =
head->next;
return;
} else {
head = NULL;
printf("List is empty now");
return;
}
} else
if(head->data != data && head->next == NULL) {
printf("%d
not found in the list\n", data);
return;
}
//prev = head;
current = head;
while(current->next != NULL && current->data != data) {
prev = current;
current =
current->next;
}
if(current->data
== data) {
prev->next =
prev->next->next;
free(current);
} else
printf("%d
not found in the list.", data);
}
int main() {
insert(10);
insert(20);
insert(30);
insert(1);
insert(40);
insert(56);
printf("Before
Removal : ");
display();
remove_data(30);
printf("After
Removal : ");
display();
return 0;
}
=========
Output
Output of the program should be −
Before Removal : [head] => 10 => 20 => 30 => 1 => 40 => 56 => [null]After Removal : [head] => 10 => 20 => 1 => 40 => 56 => [null]
==============================
Share, Subscribe, and be Follower
==============================
No comments:
Post a Comment