Scribd
Upload
33 views15 pages

Data Structure2

Data structure assignment for the students.

Uploaded by

romfar786
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
33 views15 pages

Data Structure2

Data structure assignment for the students.

Uploaded by

romfar786
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 15

COMSATS University Islamabad

(Vehari campus)
A

Assignment no:02

Submitted to:
Sir .Najeeb Ullah

Submitted by:
Iqra Fatima(FA22-BCS-155)

Subject:
Data Structures

Department:
BS-Computer Science
Question no:01
Write a code of doubly link list?

#include <iostream>
using namespace std;
// Define Node class
class Node {
public:
int data;
Node* prev;
Node* next;
};

// Define Doubly Linked List class


class DoublyLinkedList {
public:
Node* head;
Node* tail;
// Constructor
DoublyLinkedList() {
head = nullptr;
tail = nullptr;
}

/Insert at start()

int main()
{
// insert node at the front
void insertFront(struct Node* head, int data){
// allocate memory for newNode
struct Node* newNode = new Node;

newNode->data = data;
newNode->next = (*head);

// point prev to NULL


newNode->prev = NULL;
if ((*head) != NULL)
(*head)->prev = newNode;

// head points to newNode


(*head) = newNode;
}
return 0;
}

//insert at end()

// Define a structure for a node in the linked list


struct Node {
int data
Node* next;
};
// Function to create a new node with a given data value
Node* createNode(int newData) {
Node* newNode = new Node;
newNode->data = newData
newNode->next = NULL;
return newNode

void insertAtEnd(Node*& head, int newData) {


// Create a new node with the given data
Node* newNode = createNode

// If the list is empty, make the new node the head


if (head == NULL) {
head = newNode;
return;
}
Node* current = head;
while (current->next != NULL) {
current = current->next; // Move to the next node in the list
}

current->next = newNode;
}
// Function to print the elements of the linked list
void printList(Node* head) {
// Traverse the list starting from the head
Node* current = head with the head pointer
while (current != NULL) {
cout << current->data << " ";
current = current->next;
}
cout << endl;
}

int main() {
// Initialize an empty linked list (head points to NULL)
Node* head = NULL;
insertAtEnd(head, 5);
insertAtEnd(head, 10);
insertAtEnd(head, 15);
insertAtEnd(head, 20);

// Print the elements of the linked list


cout << "Linked List before deletion: ";
printList(head);
insertAtEnd(head, 42);
cout << "Linked List after insertion: ";
printList(head);
return 0;
}

//deletion at beginning ()

// Node structure for doubly linked list


struct Node {
int data;
Node* prev;
Node* next;
Node(int val) : data(val), prev(nullptr), next(nullptr) {}
};

void deleteAtBeginning(Node*& head) {


if (head == nullptr)
return;
// If only one node is present
if (head->next == nullptr) {
delete head;
head = nullptr;
return;
}

Node* temp = head;


head = head->next;
head->prev = nullptr;
delete temp;
}

// Function to print the doubly linked list


void printList(Node* head) {
while (head != nullptr) {
cout << head->data << " ";
head = head->next;
}
cout << endl;
}

int main() {
// Example usage
Node* head = new Node(1);
head->next = new Node(2);
head->next->prev = head;
head->next->next = new Node(3);
head->next->next->prev = head->next;

cout << "Original list: ";


printList(head);
deleteAtBeginning(head);
cout << "List after deletion at beginning: ";
printList(head);
return 0;
}

//deletion at desired position ()

// Node structure for doubly linked list


struct Node {
int data;
Node* prey;
Node* next;
Node(int veal) : data(val), prev(nullptr), next(nullptr) {}
};
void deleteAtPosition(Node*& head, int pos) {
if (head == nullptr)
return;
Node* temp = head;

// If position is 0 (deleting the head)


if (pos == 0) {
head = temp->next;
if (head != nullptr)
head->prev = nullptr;
delete temp;
return;
}
for (int i = 0; temp != nullptr && i < pos - 1; ++i) {
temp = temp->next;
}
if (temp == nullptr || temp->next == nullptr)
return;
Node* nodeToDelete = temp->next;
temp->next = nodeToDelete->next;
if (temp->next != nullptr)
temp->next->prev = temp;
delete nodeToDelete;
}
void printList(Node* head) {
while (head != nullptr) {
cout << head->data << " ";
head = head->next;
}
cout << endl;
}
int main() {
Node* head = new Node(1);
head->next = new Node(2);
head->next->prev = head;
head->next->next = new Node(3);
head->next->next->prev = head->next;

cout << "Original list: ";


printList(head);
deleteAtPosition(head, 1);
cout << "List after deletion at position 1: ";
printList(head);
return 0;
}

//deletion at end

// Node structure for doubly linked list


struct Node {
int data;
Node* prev;
Node* next;
Node(int val) : data(val), prev(nullptr), next(nullptr) {}
};
void deleteAtEnd(Node*& head) {
if (head == nullptr)
return;
if (head->next == nullptr) {
delete head;
head = nullptr;
return;
}
Node* temp = head;
while (temp->next->next != nullptr) {
temp = temp->next;
}

delete temp->next;
temp->next = nullptr;
}

// Function to print the doubly linked list


void printList(Node* head) {
while (head != nullptr) {
cout << head->data << " ";
head = head->next;
}
cout << endl;
}

int main() {
// Example usage
Node* head = new Node(1);
head->next = new Node(2);
head->next->prev = head;
head->next->next = new Node(3);
head->next->next->prev = head->next;

cout << "Original list: ";


printList(head);

deleteAtEnd(head);
cout << "List after deletion at end: ";
printList(head);
return 0;
}

//searching ()

struct Node {
int data;
Node* prev;
Node* next;
Node(int val) : data(val), prev(nullptr), next(nullptr) {}
};

Node* search(Node* head, int key) {


while (head != nullptr) {
if (head->data == key) {
return head;
}
head = head->next;
}
return nullptr;
}

int main() {
// Example usage
Node* head = new Node(1);
head->next = new Node(2);
head->next->prev = head;
head->next->next = new Node(3);
head->next->next->prev = head->next;

int key = 2;
Node* result = search(head, key);

if (result != nullptr) {
cout << key << " found in the list." << endl;
} else {
cout << key << " not found in the list." << endl;
}
return 0;
}

//sorting ()

struct Node {
int data;
Node* prev;
Node* next;
Node(int val) : data(val), prev(nullptr), next(nullptr) {}
};
void swapData(Node* a, Node* b) {
int temp = a->data;
a->data = b->data;
b->data = temp;
}
void bubbleSort(Node* head) {
if (head == nullptr || head->next == nullptr)
return;
Node* end = nullptr;
bool swapped;
do {
swapped = false;
Node* current = head;
while (current->next != end) {
if (current->data > current->next->data) {
swapData(current, current->next);
swapped = true;
}
current = current->next;
}
end = current;
} while (swapped);
}
void traverse(Node* head) {
cout << "Doubly linked list: ";
while (head != nullptr) {
cout << head->data << " ";
head = head->next;
}
cout << endl;
}
int main() {
// Example usage
Node* head = new Node(3);
head->next = new Node(2);
head->next->prev = head;
head->next->next = new Node(1);
head->next->next->prev = head->next;

cout << "Before sorting: ";


traverse(head);
bubbleSort(head);
cout << "After sorting: ";
traverse(head);
return 0;
}

// Forward traversal
void forwardTraversal() {
Node* temp = head;
while (temp != nullptr) {
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
}

// Reverse traversal

void reverseTraversal() {
Node* temp = tail;
while (temp != nullptr)
{
cout << temp->data << " ";
temp = temp->prev;
}
cout << endl;
}
};

int main() {
DoublyLinkedList dll;
dll.insertAtEnd(10);
dll.insertAtEnd(20);
dll.insertAtEnd(30);

cout << "Forward Traversal: ";


dll.forwardTraversal(); // Output: 10 20 30
cout << "Reverse Traversal: ";
dll.reverseTraversal();

return 0;
}

You might also like