Singly Linked List_Operations-Traversal.pptx

Linked List

1. Singly Linked List

2. A node is a data structure that contains a data item and one or more links. A link is a reference to a node An arrow of each node indicates that the reference of the next node. The reference of the first node is stored at head. The null in the link part of the last node indicates that no node follows the last node. Each node in a linked list can be implemented as a class with two instance variables data and link, placed inside a linked list class

3. class Node { public: int data; Node* next; // Default constructor Node() { data = 0; next = NULL; } // Parameterised Constructor Node(int data) { this->data = data; this->next = NULL; } }; class Linkedlist { Node* head; };

4. Operations: Traversal nodeRef walks down the list, referencing each of the list nodes in turn. The value of nodeRef is null when the traversal is finished. current = head while current is not null: print current.data current = current.next

5. Line 1: Node newNode = new Node(5, null); Line 2: newNode.next = head; Line 3: head = newNode ; Line 1 creates a new node with data 5 and link null. Line 2 makes the link part of the new node refers to the node that has been pointed by head. With line 3, now head refers to the new node. Operations: Insertion at Front

6. Operations: Insertion after First indicate where the new node will be added. Let’s say we want to add a new node after the node referred by p. newNode.next = p.next ; p.next = newNode ;

7. Operations: Insertion last if (!head) { head = newNode ; return; } Node* current = head; while (current->next) { current = current->next; } current->next = newNode ; }

8. deleteFirst(): if head is NULL: print "List is empty" else: temp = head head = head.next delete temp Delete from beginning

9. Delete at middle Traverse to element before the element to be deleted Change next pointers to exclude the node from the chain deleteMiddle (position): if head is NULL: print "List is empty" else if position == 1: deleteFirst () else: current = head prev = NULL for i from 1 to position - 1: prev = current current = current.next if current is NULL: print "Position out of bounds" return prev.next = current.next delete current

10. Delete at End Traverse to second last element Change its next pointer to null deleteLast (): if head is NULL: print "List is empty" else if head.next is NULL: delete head head = NULL else: current = head while current.next.next is not NULL current = current.next delete current.next current.next = NULL