Page 117 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Fundamentals of Data Structures Yadwinder Singh, Lovely Professional University

Notes Unit 8: Operations on Linked List

CONTENTS
Objectives
Introduction

8.1 Basic Operations on a Singly Linked List
8.1.1 Traversing the Linked List
8.1.2 Singly Linked List Insertion

8.1.3 Singly Linked List Deletion
8.2 Basic Operations on Doubly Linked Lists
8.2.1 Doubly Linked List Insertion
8.2.2 Doubly Linked List Deletion
8.3 Basic Operations on Circular Linked Lists

8.3.1 Counting Nodes in a Circular List
8.3.2 Printing the Contents of a Circular List
8.3.3 Circular Linked List Insertion

8.3.4 Circular Linked List Deletion
8.4 Summary
8.5 Keywords
8.6 Review Questions
8.7 Further Readings

Objectives

After studying this unit, you will be able to:
Discuss basic Operations on a Singly Linked List

Discuss basic Operations on Doubly Linked Lists
Discuss basic Operations on Circular Linked Lists
Introduction

Dynamic allocation is specially appropriate for building lists, trees and graphs. We used an
array for storing a collection of data items. Suppose the collection itself grows and shrinks then
using a linked list is appropriate. It allows both insertion, deletion, search. But the random
access capabilities of array is lost. Linked list is a collection of data item, where each item is
stored in a structure (node). Linked list is accessed by accessing its first node. Subsequent nodes
can be accessed by using the pointer next. So after declaring, a (empty) list is initialized to NULL.
Creating a list is done by creating nodes one after another. In this unit, we will discuss various
operations used on linked lists.

110 LOVELY PROFESSIONAL UNIVERSITY