Linked Lists Data Structures Tutorial PDF

Lecture 5: Linked Lists Dr.\ Ahmed Ibrahim Dr.\ Lamiaa Hassaan What is a Linked List?  A linked list is a linear data structure that stores a collection of data elements dynamically.  Linked list is formed of a series of connected nodes, where each node stores the data and...

Lecture 5: Linked Lists Dr.\ Ahmed Ibrahim Dr.\ Lamiaa Hassaan What is a Linked List?  A linked list is a linear data structure that stores a collection of data elements dynamically.  Linked list is formed of a series of connected nodes, where each node stores the data and the address of the next node.  Nodes represent those data elements, and links or pointers connect each node.  Each node consists of two fields, data stored in a linked list and a pointer that stores the address of its next node.  The last node contains null in its second field because it will point to no node.  A linked list can grow and shrink its size, as per the requirement. What is a Linked List?  Head: The linked list is accessed through the head node, which points to the first node in the list. The last node in the list points to NULL, indicating the end of the list. This node is known as the tail node.  Node Structure: A node in a linked list typically consists of:  Data: It holds the actual value or data associated with the node.  Next Pointer: It stores the memory address (reference) of the next node in the sequence. Linked Lists  Elements are scattered randomly through memory. head 1 4 3 2 Linked Lists  Easy to add an element (add the new link): head 1 4 3 5 2 Linked Lists  Easy to add an element (add the new link): head 1 4 3 5 2 Linked Lists  Easy to delete an element (add the new link): head 1 4 3 2 Types of Linked Lists  Singly linked list  Doubly linked list  Circular linked list Singly Linked List  In a singly linked list, each node contains a reference to the next node in the sequence. Traversing a singly linked list is done in a forward direction. Doubly Linked List  In a doubly linked list, each node contains references to both the next and previous nodes. This allows for traversal in both forward and backward directions, but it requires additional memory for the backward reference. Circular Linked List  In a circular linked list, the last node points back to the head node, creating a circular structure. It can be either singly or doubly linked. Advantages and Disadvantages of Linked Lists  Advantages of Linked Lists  Dynamic Size: Linked lists can grow or shrink dynamically, as memory allocation is done at runtime.  Insertion and Deletion: Adding or removing elements from a linked list is efficient, especially for large lists.  Flexibility: Linked lists can be easily reorganized and modified without requiring a contiguous block of memory.  Disadvantages of Linked Lists  Linear Access: Unlike arrays, linked lists do not allow direct access to elements by index. Traversal is required to reach a specific node.  Extra Memory: Linked lists require additional memory for storing the pointers, compared to arrays. Operations on Linked Lists  Insertion: Adding a new node to a linked list involves adjusting the pointers of the existing nodes to maintain the proper sequence. Insertion can be performed at the beginning, end, or any position within the list  Deletion: Removing a node from a linked list requires adjusting the pointers of the neighboring nodes to bridge the gap left by the deleted node. Deletion can be performed at the beginning, end, or any position within the list.  Searching: Searching for a specific value in a linked list involves traversing the list from the head node until the value is found or the end of the list is reached. The Node Class  Attributes (instance variables):  element: the data object  next : a reference to the next node  so it will be of type LinearNode new node element next The Node Class #include #include #include using namespace std; class Node { public: int data; Node *next; Node() { data=0; next=NULL; } }; void main() { } The Linked List Class class Linkedlist { public: Node *head; Linkedlist() { head=NULL; } } void main() { } The Linked-List Class bool isEmpty() { if (head==NULL) return true; else return false; } bool isFull() { Node *newnode=new Node(); if (newnode==NULL) return true; else return false; } Insertion of a Node in a Linked List  Given a Linked List, the task is to insert a new node in this given Linked List at the following positions:  At the front of the linked list  At its order in a sorted linked list.  At the end of the linked list.  Inserting a Node at the Beginning of Linked List  To insert a node at the start/beginning/front/head of a Linked List, we need to:  Make the new node point at the beginning of the Linked List.  Make the Head of the Linked List point at the new node. Inserting a Node at the beginning void insertatbeginning(int item) { Node *newnode=new Node(); newnode->data=item; newnode->next=head; head=newnode; }  Inserting a Node in its Order Let's insert the new node after the third node in the linked list node head insertion point 1. Locate the node preceding the insertion point , since it will have to be node modified (make current point to it) head current  Inserting a Node in its Order 2. Make the new node point to the node after node the insertion point (i.e. the node pointed to by the node that current points to) head current node 3. Make the node pointed to by current point to the new node head X current  Inserting a Node in its Order void insertsorted(int item) { Node *newnode = new Node( ); Newnode ->data = item; if (isEmpty()) { newnode -> next=NULL; head=newnode; } else { Node *temp1=head; while ((temp1 -> data > item && temp1 -> next -> data > item) || (temp1 -> data < item && temp1 -> next -> data < item) && temp1!=NULL) { temp1=temp1->next; } // coutnext = temp1->next; temp1->next = newnode; // cout next=newnode; } Deletion in a linked list  You can delete an element in a list from:  Beginning  End  Middle  Deleting the Beginning head points to the first node in the linked list, which points to the second node head Make head point to the second node (i.e. the node pointed to by the first node) head X Deleting the First Node int deletefrombeginning() { int value; Node *temp=head; if(isEmpty()) { coutnext; delete current; } } return(false); else } { while ((current >data!=value)) { previous= current; current = current >next; } previous->next = current >next; delete(current); } } else coutnext=NULL; return (value); } } Find the size of the list int count() { int c=0; Node *temp=head; while (temp!=NULL) { c++; temp=temp->next; } return(c); } Get the first element in a list. int get() { if (head!=NULL) return (head->data); else { cout data=new_item; return true; } else temp=temp->next; } return false; }