BCS301 DATA STRUCTURE

UNIT-I

Linked lists: Array Implementation and Pointer Implementation of Singly Linked

Lists, Doubly Linked List, Circularly Linked List, Operations on a Linked List.
Insertion, Deletion, Traversal, Polynomial Representation and Addition Subtraction &
Multiplications of Single variable & Two variables Polynomial.

LINKED LIST

A linked list is a sequence of data structures, which are connected together via links.
Linked List is a sequence of links which contains items. Each link contains a connection to
another link. Linked list is the second most-used data structure after array.

Following are the important terms to understand the concept of Linked List.

Link − Each link of a linked list can store a 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

Linked list can be visualized as a chain of nodes, where every node points to the next node.

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 List

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 − Last item contains link of the first element as next and the first
element has a link to the last element as 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.

Advantages of Linked Lists

• Dynamic Size: Linked lists can grow or shrink dynamically, as memory
allocation is done at runtime.
• Insertion and Deletion: Adding or removing elements from a linked list is
efficient, especially for large lists.
• Flexibility: Linked lists can be easily reorganized and modified without requiring
a contiguous block of memory.
Disadvantages of Linked Lists
• Random Access: Unlike arrays, linked lists do not allow direct access to
elements by index. Traversal is required to reach a specific node.
• Extra Memory: Linked lists require additional memory for storing the pointers,
compared to arrays.

Structure of a node:
Method

1:
struct node
{
int data;
struct node *link;
};

Node Creation
struct node
{
int data;
struct node *next;
};
struct node *head, *ptr;

ptr = (struct node *)malloc(sizeof(struct node *));

This code will create a data type Node, which will be able to store two values-:

1. int value – data

2. pointer value – address of the next node
Insertions:
To place an elements in the list there are 3 cases :
1. At the beginning
2. End of the list
3. At a given position

case 1: Insert at the beginning

head is the pointer variable which contains address of the first node and temp contains
address of new node to be inserted then sample code is

temp ->link=head;
head=temp;

After insertion:

Code for insert front:

temp=create_node(item);
if(head==NULL)
head=temp;
else
{
temp ->link=head;
head=temp;
}

case 2: Inserting end of the list

head is the pointer variable which contains address of the first node and temp contains
address of new node to be inserted then sample code is
t=head;
while(t->link!=NULL)
{
t=t->link;
}
t->link=temp;

After insertion the linked list is

Code for insert End:

temp=create_node(n);
if(head==NULL)
head=temp;
else
{
t=head;
while(t->link!=NULL)
t=t->link;
t->link=temp;
}
case 3: Insert at a position

-------------------------------------------------------------------------------------

………………………………………………………………………………….

…………………………………………………………………………………..

Example

insert node at position 3

head is the pointer variable which contains address of the first node and temp contains
address of new node to be inserted then sample code is
c=1;
while(c<pos)
{
prev=cur;
cur=cur->link;
c++;
}
prev->link=temp;
temp->link=cur;

temp=create_node(item);
if(head==NULL)
head=temp;
else
{
prev=cur=head;
if(pos==1)
{
temp->link=head;
head=temp;
}
else
{
while(c<pos)
{
c++;
prev=cur;
cur=cur->link;
}
prev->link=temp;
temp->link=cur;
}
}

Deletions:
Removing an element from the list, without destroying the integrity of
the list itself.
To place an element from the list there are 3 cases :
1. Delete a node at beginning of the list
2. Delete a node at end of the list
3. Delete a node at a given position
Case 1: Delete a node at beginning of the list
Head-----→

head is the pointer variable which contains address of the first node
sample code is
t=head;
head=head->link;
printf("node “,t->data," Deletion is success";
delete(t);

code for deleting a node at front

Case 2. Delete a node at end of the list

To delete last node , find the node using following code

struct node<T>*cur,*prev;
cur=prev=head;
while(cur->link != NULL)
{
prev=cur;
cur=cur->link;
}
prev->link=NULL;
printf("node “,curr->data," Deletion is success free(cur);
free(cur);

code for deleting a node at end of the list

CASE 3. Delete a node at a given position

Delete node at position 3

head is the pointer variable which contains address of the first node. Node to be deleted
is node containing value 30.
Finding node at position 3

c=1;
while(c<pos)
{
c++;
prev=cur;
cur=cur->link;
}

void delete_pos()
{
int i,pos;
struct node *temp,*ptr;
if(start==NULL)
{
printf("nThe List is Empty:n");
exit(0);
}
else
{
printf("nEnter the position of the node to be deleted:t");
scanf("%d",&pos);
if(pos==0)
{
ptr=start;
start=start->next ;
printf("nThe deleted element is:%dt",ptr->info );
free(ptr);
}
else
{
ptr=start;
for(i=0;i<pos;i++) { temp=ptr; ptr=ptr->next ;
if(ptr==NULL)
{
printf("nPosition not Found:n");
return;
}
}

temp->next =ptr->next ;
printf("nThe deleted element is:%dt",ptr->info );
free(ptr);
}

Traversing the list: Assuming we are given the pointer to the head of the
list, how do we get the end of the list.

void display(struct Node* node)

{
printf("Linked List: ");
// as linked list will end when Node is Null
while(node!=NULL){
printf("%d ",node->data);
node = node->next;
}
printf("\n");
}
Doubly Linked List

DOUBLY LINKED LIST

A singly linked list has the disadvantage that we can only traverse it in one direction. Many
applications require searching backwards and forwards through sections of a list. A useful
refinement that can be made to the singly linked list is to create a doubly linked list. The
distinction made between the two list types is that while singly linked list have pointers going
in one direction, doubly linked list have pointer both to the next and to the previous element
in the list.
The main advantage of a doubly linked list is that, they permit traversing or searching of
the list in both directions. In this linked list each node contains three fields.
a) One to store data
b) Remaining are self referential pointers which points to previous and
next nodes in the list

prev data next

Implementation of node using structure

Method -1:

struct node
{
int data;
struct node *prev;
struct node * next;
};

Operations on Doubly linked list:

▪ Insertion of a node
▪ Deletions of a node
▪ Traversing the list

Insertions:
To place an elements in the list there are 3 cases
1. At the beginning
2. End of the list
3. At a given Position
case 1:Insert at the beginning

head is the pointer variable which contains address of the first node and temp contains
address of new node to be inserted then sample code is

temp->next=head;
head->prev=temp;
head=temp;

case 2: Inserting end of the list

head is the pointer variable which contains address of the first node and temp contains
address of new node to be inserted then sample code is
t=head;
while(t->next!=NULL)
t=t->next;
t->next=temp;
temp->prev=t;
case 3: Inserting at a give position

insert 40 at position 2
head is the pointer variable which contains address of the first node and temp contains
address of new node to be inserted then sample code is

while(count<pos)
{
count++;
pr=cr;
cr=cr->next;
}
pr->next=temp;
temp->prev=pr;
temp->next=cr;
cr->prev=temp;
Deletions:
Removing an element from the list, without destroying the integrity of the list
itself.
To place an element from the list there are 3 cases :
1. Delete a node at beginning of the list
2. Delete a node at end of the list
3. Delete a node at a given position

Case 1: Delete a node at beginning of the list

head is the pointer variable which contains address of the first node sample code is
Page 20
t=head;
head=head->next;
head->prev=NULL;
printf(“\n deleted node is”,t->data);
delete(t);

Case 2. Delete a node at end of the list

To deleted the last node find the last node. find the node using following code

struct
dnode<T>*pr,*cr;
pr=cr=head;
while(cr->next!=NULL)
{
pr=cr;
cr=cr->next;
}
pr->next=NULL;
cout<<"dnode "<<cr->data<<" Deletion is sucess";
delete(cr);
Delete node at position 2

head is the pointer variable which contains address of the first node. Node to be deleted
is node containing value 30.
Finding node at position 2.

while(count<pos)
{
pr=cr;
cr=cr->next;
count++;
}
pr->next=cr
-
>next;
cr->next->prev=pr;

It is called the doubly linked list because there are two pointers, one point to the next node
and other points to the previous node. The operations performed in doubly linked are similar
to that of a singly linked list. Here’s the code for basic operations.

#include<stdio.h>
#include<stdlib.h>
struct Node;
typedef struct Node * PtrToNode;
typedef PtrToNode List;
typedef PtrToNode Position;
struct Node
{
int e;
Position previous;
Position next;
};

void Insert(int x, List l, Position p)

{
Position TmpCell;
TmpCell = (struct Node*) malloc(sizeof(struct Node));
if(TmpCell == NULL)
printf("Memory out of spacen");
else
{
TmpCell->e = x;
TmpCell->previous = p;
TmpCell->next = p->next;
p->next = TmpCell;
}
}

void Delete(int x, List l)

{
Position p, p1, p2;
p = Find(x, l);
if(p != NULL)
{
p1 = p -> previous;
p2 = p -> next;
p1 -> next = p -> next;
if(p2 != NULL) // if the node is not the last node
p2 -> previous = p -> previous;
}
else
printf("Element does not exist!!!n");
}

void Display(List l)
{
printf("The list element are :: ");
Position p = l->next;
while(p != NULL)
{
printf("%d -> ", p->e);
p = p->next;
}
}
int main()
{
int x, pos, ch, i;
List l, l1;
l = (struct Node *) malloc(sizeof(struct Node));
l->previous = NULL;
l->next = NULL;
List p = l;
printf("DOUBLY LINKED LIST IMPLEMENTATION OF LIST ADTnn");
do
{
printf("nn1. CREATEn 2. DELETEn 3. DISPLAYn 4. QUITnnEnter the choice :: ");
scanf("%d", &ch);
switch(ch)
{
case 1:
p = l;
printf("Enter the element to be inserted :: ");
scanf("%d",&x);
printf("Enter the position of the element :: ");
scanf("%d",&pos);
for(i = 1; i < pos; i++) { p = p->next;
}
Insert(x,l,p);
break;

case 2:
p = l;
printf("Enter the element to be deleted :: ");
scanf("%d",&x);
Delete(x,p);
break;

case 3:
Display(l);
break;
}
}
while(ch<4);
}
CIRCULARLY LINKED LIST

A circularly linked list, or simply circular list, is a linked list in which the last node is always
points to the first node.
This type of list can be build just by replacing the NULL pointer at the end of the list with a
pointer which points to the first node. There is no first or last node in the circular list.

Advantages:

Any node can be traversed starting from any other node in the list.
There is no need of NULL pointer to signal the end of the list and hence, all pointers
contain valid addresses.
In contrast to singly linked list, deletion operation in circular list is simplified as the search
for the previous
node of an element to be deleted can be started from that item itself.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
struct node {
int data;
int key;
struct node *next;
};
struct node *head = NULL;
struct node *current = NULL;
bool isEmpty(){
return head == NULL;
}
int length(){
int length = 0;

//if list is empty

if(head == NULL) {
return 0;
}
current = head->next;
while(current != head) {
length++;
current = current->next;
}
return length;
}
//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()) {
head = link;
head->next = head;
} else {

//point it to old first node

link->next = head;

//point first to new first node

head = link;
}
}

//delete first item

struct node * deleteFirst(){

//save reference to first link

struct node *tempLink = head;
if(head->next == head) {
head = NULL;
return tempLink;
}

//mark next to first link as first

head = head->next;

//return the deleted link

return tempLink;
}

//display the list

void printList(){
struct node *ptr = head;
printf("\n[ ");

//start from the beginning

if(head != NULL) {
while(ptr->next != ptr) {
printf("(%d,%d) ",ptr->key,ptr->data);
ptr = ptr->next;
}
}
printf(" ]");
}
int main(){
insertFirst(1,10);
insertFirst(2,20);
insertFirst(3,30);
insertFirst(4,1);
insertFirst(5,40);
insertFirst(6,56);
printf("Original List: ");

//print list
printList();
while(!isEmpty()) {
struct node *temp = deleteFirst();
printf("\nDeleted value:");
printf("(%d,%d) ",temp->key,temp->data);
}
printf("\nList after deleting all items: ");
printList();
}

Polynomial List

A polynomial p(x) is the expression in variable x which is in the form (axn + bxn-1 + …. +
jx+ k), where a, b, c …., k fall in the category of real numbers and 'n' is non negative
integer, which is called the degree of polynomial.

An important characteristic of polynomial is that each term in the polynomial expression

consists of two parts:

one is the coefficient

other is the exponent

Example:
10x2 + 26x, here 10 and 26 are coefficients and 2, 1 are its exponential value.
Points to keep in Mind while working with Polynomials:

The sign of each coefficient and exponent is stored within the coefficient and the
exponent itself
Additional terms having equal exponent is possible one
The storage allocation for each term in the polynomial must be done in ascending and
descending order of their exponent
Representation of Polynomial

Polynomial can be represented in the various ways. These are:

By the use of arrays
By the use of Linked List

Representation of Polynomials using Arrays

There may arise some situation where you need to evaluate many polynomial expressions
and perform basic arithmetic operations like: addition and subtraction with those numbers.
For this you will have to get a way to represent those polynomials. The simple way is to
represent a polynomial with degree 'n' and store the coefficient of n+1 terms of the
polynomial in array. So every array element will consists of two values:

Coefficient and
Exponent

Representation of Polynomial Using Linked Lists

A polynomial can be thought of as an ordered list of non zero terms. Each non zero term is
a two tuple which holds two pieces of information:

The exponent part

The coefficient part

Adding two polynomials using Linked List

Given two polynomial numbers represented by a linked list. Write a function that add these
lists means add the coefficients who have same variable powers.

Input:
1st number = 5x^2 + 4x^1 + 2x^0
2nd number = 5x^1 + 5x^0
Output:
5x^2 + 9x^1 + 7x^0
Input:
1st number = 5x^3 + 4x^2 + 2x^0
2nd number = 5x^1 + 5x^0
Output:
5x^3 + 4x^2 + 5x^1 + 7x^0