[go: up one dir, main page]
Scribd
Upload
14 views8 pages

DSA lab 7a

The document outlines a lab experiment for implementing a single linked list in C++ as part of the Electrical Engineering curriculum at the National University of Technology, Islamabad. It includes objectives, a definition of linked lists, node structure, and various functions for manipulating linked lists such as appending nodes, traversing, inserting, and deleting nodes. The document also provides sample code for implementing these functions in C++.

Uploaded by

sidraashraf
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
14 views8 pages

DSA lab 7a

The document outlines a lab experiment for implementing a single linked list in C++ as part of the Electrical Engineering curriculum at the National University of Technology, Islamabad. It includes objectives, a definition of linked lists, node structure, and various functions for manipulating linked lists such as appending nodes, traversing, inserting, and deleting nodes. The document also provides sample code for implementing these functions in C++.

Uploaded by

sidraashraf
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/ 8

National University of Technology

Islamabad, Pakistan

Electrical Engineering Department

EE-2006 Data Structure and Algorithms Lab Semester: V

EXPERIMENT NO.07: Implementation of Single Linked List

OBJECTIVE:

● Understanding the concept of Linked list


● Implementing single linked list in C++
● Implementing Operations on single linked list (Traverse through Node, Add node, delete
node)

Date of Experiment: ________________

Submitted on: ________________

Obtained Marks:

Remarks:

Instructor’s Signature: ______________________________

What is a linked list?


In computer science, a linked list is a data structure consisting of a group of nodes which
together represent a sequence. Under the simplest form, each node is composed of data
and a pointer (in other words, a link) to the next node in the sequence.

Structure of a Node in a Linked List

struct Node

int data; // the data variable for storing a value.

Node * next; // the next pointer of type “Node”, pointing to the next Node
in the sequence.

};

1. Appending Nodes at the End.


Lets make a function named appendNode() which is given input an int and a
reference to the head pointer (i.e. a Node*& reference to the head pointer), adds a
new node at the end of the list with the standard 3-step-link-in:
a. create a new node,
b. set its “next pointer” to point to NULL,
c. Then find out the end node and insert the new node after it.

Write a function printList() that takes input a linked list's head pointer and iterates
through it and prints all node values in the sequence.

2. Keeping track of our list’s length.


Lets make a function length() which when called returns the number of nodes in the
list.

3. Making a default list.


Make a function buildOneTwoThree() that allocates and returns a list {1, 2, 3}, uses
the appendNode () function implemented in 1 thrice to add 3 nodes.

4. Getting a node at a certain index


Write a GetNth() function that takes input a linked list and an integer index and
returns the node at that index position.

5. Inserting a node in ascending order


Write a function insertASC() which takes input a linked list, and an integer value,
then
1. makes a new node using that integer value
2. inserts it after finding a suitable location in the list, keeping all nodes of the list
in ascending order.

6. Joining two linked lists together.

LIST A  LIST B 

LISTS A & B UNITED! 

Write a function that takes input two linked lists, and returns a union of them. Use
buildOneTwoThree() function implemented in 3 to get two lists and pass them to this
function to get the union.
8. Deleting a list

Remember, since the nodes are created on a heap, its your responsibility to release
the memory a list is occupying by deleting each and every node in that list.

Write a function named deleteList() which is when given a pointer to a list deletes all
of its nodes.

1) Appending a Node in the List


void appendNode(float);
Create a new node.
Store data in the new node.
If there are no nodes in the list
Make the new node the first node.
Else
Traverse the List to Find the last node.
Add the new node to the end of the list.
End If.
2) Traversing the List
void displayNode(float);

Assign List head to node pointer.


While node pointer is not NULL
Display the value member of the node pointed to by node pointer.
Assign node pointer to its own next member.
End While
3) Inserting in the List
void insertNode(float);
Create a new node.
Store data in the new node.
If there are no nodes in the list
Make the new node the first node.
Else
Find the first node whose value is greater than or equal
the new value, or the end of the list (whichever is first).
Insert the new node before the found node, or at the end
of the list if no node was found.
End If.
4) Destroying the List
. Destroying the list should release all the memory used by the
list.
. It does so by stepping through the list, deleting each node one-
by-one. The code is shown on the next slide.

Implementation
#include <iostream>
Using namespace std;
// Node structure for the linked list
struct Node {
int data;
Node* next;
};

// Function to append a new element to the linked list


void append(Node*& head, int value) {
Node* newNode = new Node{value, nullptr};

if (head == nullptr) {
// If the list is empty, make the new node the head
head = newNode;
} else {
// Traverse the list to find the last node and append the new
node
Node* current = head;
while (current->next != nullptr) {
current = current->next;
}
current->next = newNode;
}
}

// Function to display the elements of the linked list


void display(const Node* head) {
const Node* current = head;

cout << "Linked List: ";


while (current != nullptr) {
cout << current->data << " ";
current = current->next;
}
cout << endl;
}
// Function to traverse the linked list
void traverse(const Node* head) {
const Node* current = head;

std::cout << "Traversal: ";


while (current != nullptr) {
std::cout << current->data << " ";
current = current->next;
}
std::cout << std::endl;
}

// Function to insert a new element at a specific position in the linked


list
void insert(Node*& head, int value, int position) {
Node* newNode = new Node{value, nullptr};

if (position == 0) {
// Insert at the beginning
newNode->next = head;
head = newNode;
} else {
// Traverse the list to the position-1 node
Node* current = head;
for (int i = 0; i < position - 1 && current != nullptr; ++i) {
current = current->next;
}}}
int main() {
// Create a linked list
Node* myList = nullptr;

// Append elements to the linked list


append(myList, 1);
append(myList, 2);
append(myList, 3);
append(myList, 4);

// Display the elements of the linked list


display(myList);

// Traverse the linked list


traverse(myList);

// Insert an element at a specific position


insert(myList, 3, 2);

// Display the elements after insertion


display(myList);
// Clean up: Free the memory allocated for the linked list
Node* current = myList;
while (current != nullptr) {
Node* nextNode = current->next;
delete current;
current = nextNode;
}

return 0;
}

You might also like