Singly linked list

Linked List Amar Jukuntla, Assistant Professor, Department of CSE, VFSTR University 1

Index • Introduction • Linked List implementation • Node Creation • Insertion at Beginning • Insertion at End of the List • Insertion at given Position • Deletion at Beginning • Deletion at End of the List • Deletion at given Position 2

Introduction • A linked list is a data structure that consists of sequence of nodes. Each node is composed of two fields: data field and reference field which is a pointer that points to the next node in the sequence. 3

Continue… • Each node in the list is also called an element. The reference field that contains a pointer which points to the next node is called next pointer or next link. • A head pointer is used to track the first element in the linked list, therefore, it always points to the first element. • The following picture illustrates a linked list. 4

Continue… • The linked list data structure is designed to be efficient for insertion or removal of elements from any position in the list. • However other operations such as getting the last element or finding an element that stores specific data requires scanning most or all the elements in the list. • A linked list is also used to implement other data structures like stack and queue. 5

Linked List implementation • We can model a node of the linked list using a structure as follows: • The node structure has two members: • data stores the information • next pointer holds the address of the next node. 1 2 3 4 typedef struct node{ int data; struct node* next; }; 6

Add a node at the beginning of the linked list • First, we declare a head pointer that always points to the first node of the list. • To add a node at the beginning of the list: • First, we need to create a new node. We will need to create a new node each time we want to insert a new node into the list so we can develop a function that creates a new node and return it. 1node* head; 7

node* create(int data, node* next) { node* new_node = (node*)malloc(sizeof(node)); if(new_node == NULL) { printf("Error creating a new node.n"); exit(0); } new_node->data = data; new_node->next = next; return new_node; } 9

Adding a node at beginning •Steps to insert node at the beginning of singly linked list • Create a new node, say newNode points to the newly created node. • Link the newly created node with the head node, i.e. the newNode will now point to head node. • Make the new node as the head node, i.e. now head node will point to newNode 11

Continue… newNode->data = data; // Link data part newNode->next = head; // Link address part head = newNode; 15

Insert node at Last / End Position in Singly Linked List •Inserting node at start in the Single Linked List (Steps): • Create New Node • Fill Data into “Data Field“ • Make it’s “Pointer” or “Next Field” as NULL • Node is to be inserted at Last Position so we need to traverse SLL upto Last Node. • Make link between last node and newnode 16

Insert Node at given Position 19

Continue… • Check if the given prev_node is NULL • Allocate new node • Put in the data • Make next of new node as next of prev_node. • Move the next of prev_node as new_node 20

Deletion of a Node at Beginning 22

Continue… •Steps to delete first node from Singly Linked List • Copy the address of first node i.e. head node to some temp variable say toDelete. • Move the head to the second node of the linked list i.e. head = head->next. • Disconnect the connection of first node to second node. • Free the memory occupied by the first node. 23

Step 1: Copy the address of first node 24

Step 2: Move the head to the second node 25

Step 3: Disconnect the connection of first node 26

28 delNode= head; head=head->next; free(delNode);

Deletion of a Node at End of the List • Steps to delete last node of a Singly Linked List • Traverse to the last node of the linked list keeping track of the second last node in some temp variable say secondLastNode. • If the last node is the head node then make the head node as NULL else disconnect the second last node with the last node i.e. secondLastNode->next = NULL. • Free the memory occupied by the last node. 29

Step 1: Traverse to the last node of the linked list keeping track of the second last node 30

Step 2: secondLastNode->next = NULL. 31

Step 3: Free the memory occupied by the last node 32

33 void deletionAtE() { struct node *temp, *temp1; if(head== NULL) { printf("Node Already Nulln"); }else{ temp=head; temp1=NULL; while(temp->next !=NULL){ temp1=temp; temp=temp->next; } if(temp1!=NULL){ temp1->next=NULL; } if(temp==head) head=NULL; free(temp); printf("Deletedn"); } }

Deletion at given Position •Steps to delete middle node of Singly Linked List •Traverse to the nth node of the singly linked list and also keep reference of n-1th node in some temp variable say prevnode. 34

Continue… • Reconnect the n-1th node with the n+1th node i.e. prevNode->next = toDelete->next (Where prevNode is n-1th node and toDelete node is the nth node and toDelete->next is the n+1th node). 35

Continue… • Free the memory occupied by the nth node i.e. toDelete node. 36

Continue… // Find previous node of the node to be deleted for (int i=0; prev!=NULL && i<pos-1; i++) prev = prev->next; for (int i=0; next!=NULL && i<pos+1; i++) next = next->next; prev->next=next; 37

Reverse of a List struct node *current, *prev,*next; current=head; prev=NULL; while(current!=NULL) { next=current->next; current->next=prev; prev=current; current=next; } head=prev; 38

Next Session • Doubly Linked List • Circular Linked List 39

Singly linked list

In this document

More Related Content

What's hot

Similar to Singly linked list

More from Amar Jukuntla

Recently uploaded

Singly linked list