NAME : MAHEDI HASSAN
STUDENT ID : 20183290535
SUBJECT : Data Structure
SCHOOL : Information Science and Engineering
MAJOR : Computer Science & Technology
TEACHER : TEACHER YI
Session 3
Part 1: Creat a linked list
Introduction
A linked list is a way to store a collection of elements. Like an array these can be character or
integers. Each element in a linked list is stored in the form of a node.
Node:
A node is a collection of two sub-elements or parts. A data part that stores the element and
a next part that stores the link to the next node.
Linked List:
A linked list is formed when many such nodes are linked together to form a chain. Each node points
to the next node present in the order. The first node is always used as a reference to traverse the list
and is called HEAD. The last node points to NULL.
Declaring a Linked list :
In C language, a linked list can be implemented using structure and pointers .
struct LinkedList{
int data;
struct LinkedList *next;
};
The above definition is used to create every node in the list. The data field stores the element and
the next is a pointer to store the address of the next node.
Noticed something unusual with next?
In place of a data type, struct LinkedList is written before next. That's because its a self-referencing
pointer. It means a pointer that points to whatever it is a part of. Here next is a part of a node and it
will point to the next node.
Code
Code 1:
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node *next;
};
struct Node* head = NULL;
void insert(int new_data) {
struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = head;
head = new_node;
}
void display() {
cout<<"The linked list is: ";
struct Node* pre;
pre = head;
while (pre != NULL) {
cout << pre->data << " ";
pre = pre->next;
}
}
int main() {
insert(3);
insert(1);
insert(7);
insert(2);
insert(11);
insert(17);
cout<<"The linked list is: ";
struct Node* pre;
pre = head;
while (pre != NULL) {
cout << pre->data << " ";
pre = pre->next;
}
return 0;
}
Result
Session 3
Part 2: Head insertion
Introduction
Inserting a new element into a singly linked list at beginning is quite simple. We just need to
make a few adjustments in the node links. There are the following steps which need to be
followed in order to inser a new node in the list at beginning.
o Allocate the space for the new node and store data into the data part of the node. This will
be done by the following statements.
1. ptr = (struct node *) malloc(sizeof(struct node *));
2. ptr → data = item
o Make the link part of the new node pointing to the existing first node of the list. This will
be done by using the following statement.
1. ptr->next = head;
o At the last, we need to make the new node as the first node of the list this will be done by
using the following statement.
1. head = ptr;
Algorithm
o Step 1: IF PTR = NULL
Write OVERFLOW
Go to Step 7
[END OF IF]
o Step 2: SET NEW_NODE = PTR
o Step 3: SET PTR = PTR → NEXT
o Step 4: SET NEW_NODE → DATA = VAL
o Step 5: SET NEW_NODE → NEXT = HEAD
o Step 6: SET HEAD = NEW_NODE
o Step 7: EXIT
Code
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node *next;
};
struct Node* head = NULL;
void insert(int new_data) {
struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = head;
head = new_node;
}
void display() {
cout<<"The linked list is: ";
struct Node* pre;
pre = head;
while (pre != NULL) {
cout << pre->data << " ";
pre = pre->next;
}
}
int main() {
insert(3);
insert(1);
insert(7);
display();
return 0;
}
Result
