Page 118 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Unit 8: Operations on Linked List

8.1 Basic Operations on a Singly Linked List Notes

The basic operations on a singly linked list include:

Traversing the list
Inserting an item in the list
Deleting an item from the list

8.1.1 Traversing the Linked List

Let us assume that the head points to the first node of the list. To traverse the list we do the
following.

Follow the pointers.
Display the contents of the nodes (or count) as they are traversed.
Stop when the next pointer points to NULL.

Figure 8.1: Traversing the Linked Lists

Source: http://www.csie.ntu.edu.tw/~hsinmu/courses/lib/exe/fetch.php?media=dsa_12spring:
dsame_chap3.pdf
The ListLength() function takes a linked list as input and counts the number of nodes in the list.

Example: Below function can be used for printing the list data with extra print function.
int ListLength(stnict ListNode *head) f struct ListNode *current = head;
int count = 0;

8.1.2 Singly Linked List Insertion

Insertion into a singly-linked list has three cases:

Inserting a new node before the head (at the beginning)
Inserting a new node after the tail (at the end of the list)
Inserting a new node at the middle of the list (random location)

Notes To insert an element in the linked list at some position p, assume that after inserting
the element the position of this new node is p.
Inserting a Node in Singly Linked List at the Beginning

In this case, a new node is inserted before the current head node. Only one next pointer needs to
be modified (new node’s next pointer) and it can be done in two steps.

LOVELY PROFESSIONAL UNIVERSITY 111