Page 86 - DCAP407_DATA_STRUCTURE

Mithilesh Kumar Dubey, Lovely Professional University Unit 5: Introduction to Linked List

Unit 5: Introduction to Linked List

CONTENTS
Objectives

Introduction
5.1 Basics of Linked List
5.2 Representation of Linked List in Memory
5.3 Types of Linked Lists
5.3.1 Singly-Linked List
5.3.2 Doubly-Linked List

5.3.3 Circular Linked List
5.3.4 Circular Doubly-Linked List
5.4 Summary
5.5 Keywords
5.6 Self Assessment
5.7 Review Questions
5.8 Further Readings

Objectives
After studying this unit, you will be able to:

• Understand the basics of linked list
• Analyze the representation of linked list in memory
• Discuss the types of linked lists
Introduction

Linked lists are the most common data structures. They are referred to as an array of connected objects
where data is stored in the pointer fields. Linked lists are useful when the number of elements to be
stored in a list is indefinite.

Consider the list of five students in an attendance register - Amar, Divya, Prateek,
Sunil, and Yash. If you wish to add the name “Rita” to the list, then you have to
create space for the new name in the list. A linked list performs this by moving
the first three names in the list to the left and the last two names to the right.
Linked lists are similar to arrays as they both are used to store a collection of data. The drawbacks of
using arrays are:
1. Once the elements are stored, it becomes difficult to insert or delete an element at any position in a
list.
2. Arrays have fixed size. Hence, if the memory allocated is too large than the actual data, unused
portion of the memory is wasted. If the allocated memory is less, it will result in loss of data due to
inadequate memory.

LOVELY PROFESSIONAL UNIVERSITY 79