CSE 2215: Data Structures and Algorithms I
Sherajul Arifin
Lecturer, Department of Computer Science and Engineering,
United International University
Linked List
●A linked list is a linear collection of data elements (called nodes), where
the linear order is given by means of pointers.
●Each node is divided into 2 parts:
▪1st part contains the information of the element.
▪2nd part is called the link field or next pointer field which contains the
address of the next node in the list.
struct node{
int value;
struct
node
*next;
}
2
3
4
Basic Operations
●Insert: Add a new node in the first, last or interior of the list.
●Delete: Delete a node from the first, last or interior of the list.
●Search: Search a node containing particular value in the linked list.
5
Linked List (Insertion)
• Add a new node at the first, last or interior of a linked list
6
Insert First
●To add a new node to the head of the linear linked list, we
need to construct a new node that is pointed by pointer
newitem.
●Assume there is a global variable head which points to the
first node in the list.
●The new node points to the first node in the list. The head
is then set to point to the new node.
7
Insert First
●Step 1. Create a new node that is pointed by pointer newItem.
●Step 2. Link the new node to the first node of the linked list.
●Step 3. Set the pointer head to the new node.
8
Insert First
struct node{
int value;
struct node
*next;
};
struct node *head;
void insertHead(){
//create a new node
struct node *newItem;
newItem=(struct node *)malloc(sizeof(struct node));
newItem->value = 10;
newItem->next = NULL;
//insert the new node at the head
newItem->next = head;
head = newItem;
}
9
Insert Last
●Step1. Create the new node.
●Step2. Set a temporary pointer last to point to the last
node.
●Step3. Set last to point to the new node.
10
Insert Last
struct node{
int value;
void insertTail(){
//create a new node to be inserted struct node
struct node *newItem; *next;
newItem=(struct node *)malloc(sizeof(struct node));
};
newItem->value = 10; newItem->next = NULL;
struct node *head;
// set last to point to the last node of the list
struct node *last = head;
while (last->next != NULL)
last = last->next;
last->next = newItem;
}
11
Insert Middle
(after a desired node)
void insertMiddle(int num){
//create a new node to be inserted
struct node *newItem;
newItem=(struct node *)malloc(sizeof(struct node));
newItem->value = 10;
newItem->next = NULL;
// set prev to point to the desired node of the list
struct node *prev = head;
while (prev->value != num){
prev = prev->next;
}
newItem->next = prev->next;
prev->next = newItem;
}
12
Printing Linked List
void printList()
{
if (head == NULL) // no list at all
return;
struct node *cur = head;
while (cur != NULL)
{
printf("%d \t", cur->value);
cur = cur->next;
}
}
13
Deletion from a Linked List
●Deletion can be done
■At the first node of a linked list.
■At the end of a linked list.
■Within the linked list.
14
Delete First
• To delete the first node of the linked list, we not only want to
advance the pointer head to the second node
• But we also want to release the memory occupied by the abandoned
node.
15
Delete First
●Step1. Initialize the pointer cur point to the first node of the list.
●Step2. Move the pointer head to the second node of the list.
●Step3. Remove the node that is pointed by the pointer cur.
16
Delete First
void deleteHead()
{
struct node *cur;
if (head = = NULL) //list empty
return;
cur = head; // save head pointer
head = head->next; //advance head
free(cur);
}
17
Delete Last
• To delete the last node in a linked list, we use a local
variable, cur, to point to the last node. We also use another
variable, prev, to point to the second last node in the linked
list.
18
Delete Last
●Step1. Initialize pointer cur to point to the first node of the list, while the pointer
prev has a value of NULL.
●Step2. Traverse the entire list until the pointer cur points to the last node of the
list.
●Step3. Set NULL to next field of the node pointed by the pointer prev.
●Step4. Remove the last node that is pointed by the pointer cur.
19
Delete Last
void deleteTail(){
if (head == NULL) //list empty
return;
struct node *cur = head;
struct node *prev = NULL;
while (cur->next != NULL){
prev = cur;
cur=cur->next;
}
if (prev != NULL) prev->next = NULL;
else head = NULL;
free(cur);
}
20
Delete Any
• To delete a node that contains a particular value x in a linked list,
we use a local variable, cur, to point to this node, and another
variable, prev, to hold the previous node.
21
Delete Any
●Step1. Initialize pointer cur to point to the first node of the list, while the pointer
prev has a value of null.
●Step2. Traverse the entire list until the pointer cur points to the node that contains
value of x, and prev points to the previous node.
●Step3. Link the node pointed by pointer prev to the node after the cur’s node.
●Step4. Remove the node pointed by cur.
22
Delete Any
void deleteAny( int x){
if (head == NULL) //list empty
return;
struct node *cur = head;
struct node *prev = NULL;
while (cur->value != x){
prev = cur;
cur=cur->next;
}
if (prev != NULL)
prev->next = cur->next;
else head = NULL;
}
23
Search
Can you write an algorithm for search?
• Can you reuse any previously written code segment?
• How will you handle the case when an element is not present in
the list?
24
Thank you!
