Data Structure and Algorithms based on the Object-oriented programming (OOP) where some are the base of OOP for instant inheritance, polymorphism, Encapsulation and Abstraction etc. Now we will start learning data structures in Programming languages such as Linked list, arrays, Structs, Classes, Queues, Stacks etc.
Today’s Concept:
Linked List
Prerequisite of this Lab is all those students who have basic concepts on C++ Programming such as Syntax of Language, concept of functions, pointers, datatypes etc. Visual Studio 2012 and onward version will be used for implementation and programming tasks assigned in the Lab.
Linked List is one of the
important concepts of Programming in data structures and Algorithms. Linked
list based on pointers concept which you have studies in your previous semester’s
courses such as fundamentals of programming or OOP (Object oriented programming)
etc. just recalling the main idea of pointers before starting the today's Lab Manual.
Pointers are the special variables
in C++ (and other languages also using the same concept) which does not have
any return type of its own it means when you declaring the pointer you actually
telling the pointer to point that type of variable for instant if I declare int
* ptr (* shows its pointer) that means now this pointer will point only integer
variable or it can store address of integer variables.
Syntax of pointers in C++:
Datatype of pointer to point *pointerName
= NULL or &Variable name
Datatypes such as int, float,
char etc.
Initialisation of Pointers:
There are two simple ways to initialise pointer will Address or NULL
- int *ptr=NULL
- int *ptr=&variable_name
Linear Data Structures
A Linear data structure have data elements arranged in sequential manner and each member element is connected to its previous and next element.Such data structures are easy to implement as computer memory is also sequential. Examples of linear data structures are List, Queue, Stack, Array etc.
Non-linear Data Structures
A non-linear data structure has no set sequence of connecting all its elements and each element can have multiple paths to connect to other elements.Such data structures are not easy to implement but are more efficient in utilising computer memory. Examples of non-linear data structures are Tree, BST, Graphs etc.
Linked List is a linear
data structure in which elements not stored at the consecutive memory locations
all elements of lined list connects with the links called pointers as shown in
the below diagram
So, we can simply say that linked list consists of two main things one is Nodes which contained data and other thing which connects that nodes called Links Pointer.
- Arrays data structures stored data in consecutive memory blocks that means if you store 10 variable then they will be get stored in same 10 blocks but on the other hands linked list stores data in different memory blocks but connect them using links
- In arrays you can access your stored values using indexes but in the linked list you must start from head and go all the way to the end to find your value. Accessing time of Array is better and faster than linked list
- Operations like insertion and deletion in arrays consume a lot of time. On the other hand, the performance of these operations in Linked lists is fast.
- Arrays are of fixed size not change in runtime, but linked lists are dynamic and can be change in runtime. Arrays gets its memory allocate during compile time, linked list gets its memory allocated during runtime or execution time, additionally memory utilisation is inefficient in the array but on the other hands memory utilisation is efficient in the linked list.
Linked lists have following limitations:
- Random access in not provided by lined list data structure
- Extra memory for the pointer required
- Arrays have better cache locality as they are fixed in size
and have the consecutive blocks that can make a pretty big difference in
performance
In link list there are major 3 operations insertion, deletion, and searching all are given below but one operation is very important and have many cases such as Deleting a Node.
Deletion of the Linked List (Node):
Deletion of the node (value) from list is very tricky sometimes for instant value can be present of different location so major task is to locate the value and then perform operation:
Deletion have two cases in general:
- Value present on the start of the list
- value present middle or anywhere of the list
Linked List Implementation Example using C++:
Node.h
#include <iostream>
{
public:
int
data;
node *next;
};
ListInsertion.cpp
#include"Node.h"
class ListInsertion
{
private:
node *head,*tail;
public:
ListInsertion()
{
head = NULL;
tail = NULL;
}
void
add_node(int n)
{
node *tmp = new node;
tmp->data= n;
tmp->next = NULL;
if(head
== NULL)
{
head = tmp;
tail = tmp;
}
else
{
tail->next = tmp;
tail = tail->next;
}
}
void
display()
{
node *tmp;
tmp = head;
while
(tmp != NULL)
{
cout << tmp->data <<
endl;
tmp = tmp->next;
}
}
void Search(int number)
{
node *tmp;
tmp = head;
while (tmp != NULL)
{
if(number == tmp->data)
{
cout << "number is ="<<tmp->data << endl;
break;
}
tmp = tmp->next;
}
}
void deleteNode(int key)
{
node* temp = start, *prev;
//case one where value lies on the start
if
(temp != NULL && temp->age== key)
{
start = temp->link; //change start
delete(temp); // delete value
return;
}
//Case 2 where value can be any where last or middle
while
(temp != NULL && temp->age != key)
{
prev = temp;
temp = temp->link;
}
// null returns if value not present
if
(temp == NULL) return;
// Deletion is the node is present anywhere other than
start
prev->link = temp->link;
delete(temp);
}
};
int main()
{
ListInsertion a;
a.add_node(1);
a.add_node(2);
a.display();
system("pause");
return 0;
}
Lab Task Activity Single Linked List:
- Write your understanding on the word document about linked list using C++ please read the manual and just write what you understand don't try to copy and past from other sources.
- Create C++ program to run same code given as Example and take screenshot for submission.
- Create C++ program to implement linked list add values in the linked list using loop and terminate when user enters 0, and print them on the console using display.
- Create C++ program to delete value in the Linked List. you can create member function in the class for deletion.
- Create C++ program to merge two linked list's values. for instant you have two linked lists 1,2,3 and 4,5,6 your task is to merge their values and print together 1,2,3,4,5,6 etc.
Doubly Linked List:
Doubly linked list is a type of linked list in which each node has a data part and two linked for storing previous node and front node. The previous link points to the previous node in the list and the front link points to the next node in the list. The first node of the list has its previous link pointing to NULL similarly the last node of the list has its next node pointing to NULL.
Lab Task Activity doubly Linked List:
- implement doubly linked list as we discussed in class lecture using single linked list code. there are many implementations are available but you must follow the simply one as we discussed.
Node.h
#include<iostream>
using namespace std;
class node
{
public:
//Data Part
int
age;
//Link Part
node *next;
node *pre;
};
Link.h
#include"node1.h"
class link
{
private:
node *head,*ftail,*ptail;
public:
link()
{
head=NULL;
ftail=NULL;
ptail=NULL;
}
void
insertfront(int a)
{
node* newnode=new node;
newnode->age=a;
newnode->next=NULL;
newnode->pre=NULL;
if(head==NULL)
{
head=newnode;
ftail=newnode;
ptail=newnode;
}
else
{
ftail->next=newnode;
newnode->pre=ftail;
ftail=newnode;
}
}
void
insertpre(int a)
{
node* newnode=new node;
newnode->age=a;
newnode->next=NULL;
newnode->pre=NULL;
if(head==NULL)
{
head=newnode;
ftail=newnode;
ptail=newnode;
}
else
{
ptail->pre=newnode;
newnode->next=ptail;
ptail=newnode;
}
}
void
displayF()
{
node*tmp=head;
while(tmp != NULL)
{
cout<<tmp->age<<endl;
tmp=tmp->next;
}
}
void
displayp()
{
node*tmp=head;
while(tmp != NULL)
{
cout<<tmp->age<<endl;
tmp=tmp->pre;
}
}
};
Main.h
#include"link.h"
int main()
{
link obj1;
obj1.insertfront(12);
obj1.insertfront(2);
obj1.insertfront(1);
obj1.displayF();
cout<<"back"<<endl;
obj1.insertpre(100);
obj1.insertpre(200);
obj1.displayp();
system("pause");
return 0;
}
Tasks Submission Linked List:
This comment has been removed by the author.
ReplyDelete#include"d_node.h"
ReplyDeleteclass insert_f{
d_node * head;
d_node * ftail;
d_node * ptail;
public:
insert_f()
{
head=NULL;
ftail=NULL;
ptail=NULL;
}
void addf( int n )
{
d_node * temp= new d_node();
temp->data=n;
temp->next=NULL;
temp->prev=NULL;
if(head==NULL)
{
head=temp;
ftail=temp;
ptail=temp;
}
else{
ftail->next=temp;
temp->prev=ftail;
ftail=temp;
}
}
void show_f(){
d_node * temp;
temp = head;
while(temp!=NULL)
{
cout<data<next;
}
}
};
int main()
{
insert_f o;
o.addf(1);
o.addf(2);
o.addf(3);
o.addf(4);
o.show_f();
return 0;
}
//working code just for forword purpose For Doubly link list
Post a Comment