Page 98 - DCAP407_DATA_STRUCTURE

Manpreet Kaur, Lovely Professional University Unit 6: Linked List Operations

Unit 6: Linked List Operations

CONTENTS
Objectives
Introduction
6.1 Traversing a Linked List
6.2 Searching a Linked List

6.3 Inserting a Node into a Linked List
6.3.1 Inserting a Node at the Beginning of a List
6.3.2 Inserting a Node after a Given Node
6.3.3 Inserting a Node in a Circular Linked List
6.4 Deleting a Node from a Linked List
6.4.1 Deleting a Node Following a Given Node
6.5 Summary

6.6 Keywords
6.7 Self Assessment
6.8 Review Questions
6.9 Further Readings

Objectives
After studying this unit, you will be able to:
• Explain the traversing of a linked list
• Describe the process of searching a linked list

• Explain the method of inserting a node into a linked list
• Discuss the process of deleting a node from a linked list
Introduction

In the previous unit, we discussed the fundamentals of linked list. This unit deals with linked list
operations for performing different functions. Data processing involves organizing data into lists. One
way to store such data is by means of arrays. But, in arrays the process of insertion and deletion are
expensive. Arrays occupy only a block of memory space and it is not possible to extend the size of the
array.
The alternative way of storing the data can be done in a list format. The elements are stored in a list that
contains a field called a link or a pointer. The pointer contains the address of the next element in the list.
In linked list, it is not essential that consecutive elements occupy contiguous space in memory. Hence it
is easy to traverse and insert and delete items in the linked list.
6.1 Traversing a Linked List
Traversing a linked list involves processing every node present in a list. It is useful to perform various
operations such as, reversing the order of elements present in a list, sorting the elements in ascending or
descending order, and so on.

LOVELY PROFESSIONAL UNIVERSITY 91