Page 99 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Fundamentals of Data Structures Balraj Kumar, Lovely Professional University

Notes Unit 7: Linked Lists

CONTENTS
Objectives

Introduction
7.1 Concept of Linked Lists
7.1.1 Designing the Node of a Linked List

7.1.2 Creating the First Node
7.1.3 Adding the Second Node and Linking
7.1.4 Representation of Linked Lists in Memory

7.2 Types of Linked Lists
7.2.1 Singly Linked List
7.2.2 Doubly Linked List

7.2.3 Multilinked List
7.2.4 Circular Linked List
7.3 Summary

7.4 Keywords
7.5 Review Questions
7.6 Further Readings

Objectives

After studying this unit, you will be able to:
Discuss the concept of linked lists
Explain the representation of linked list in memory

Discuss different types of Linked Lists
Introduction

Static arrays are structures whose size is fixed at compile time and therefore cannot be extended
or reduced to fit the data set. A dynamic array can be extended by doubling the size but there is
overhead associated with the operation of copying old data and freeing the memory associated
with the old data structure. One potential problem of using arrays for storing data is that arrays
require a contiguous block of memory which may not be available, if the requested contiguous
block is too large. However the advantages of using arrays are that each element in the array can
be accessed very efficiently using an index. However, for applications that can be better managed
without using contiguous memory we define a concept called “linked lists”.

92 LOVELY PROFESSIONAL UNIVERSITY