Page 100 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Unit 7: Linked Lists

7.1 Concept of Linked Lists Notes

A linked list is a collection of objects linked together by references from one object to another
object. By convention these objects are named as nodes. So the basic linked list is collection of
nodes where each node contains one or more data fields AND a reference to the next node. The
last node points to a NULL reference to indicate the end of the list.
Figure 7.1: Linked list

A0 A1 A2 A3

first last

Source: http://www.cs.cmu.edu/~ab/15-123S09/lectures/Lecture%2010%20-%20%20Linked%20
List%20Operations.pdf
The entry point into a linked list is always the first or head of the list.

Did u know? Head is NOT a separate node, but a reference to the first Node in the list.

If the list is empty, then the head has the value NULL. Unlike Arrays, nodes cannot be accessed
by an index since memory allocated for each individual node may not be contiguous. We must
begin from the head of the list and traverse the list sequentially to access the nodes in the list.
Insertions of new nodes and deletion of existing nodes are fairly easy to handle. Recall that array
insertions or deletions may require adjustment of the array (overhead), but insertions and
deletions in linked lists can be performed very efficiently.
Linked lists have advantages and disadvantages. The advantage of linked lists is that they can be
expanded in constant time.

!

Caution To create an array we must allocate memory for a certain number of elements.
To add more elements to the array then we must create a new array and copy the old array into
the new array. This can take lot of time.
We can prevent this by allocating lots of space initially but then you might allocate more than
you need and wasting memory. With a linked list we can start with space for just one element
allocated and add on new elements easily without the need to do any copying and reallocating.

There are a number of issues in linked lists. The main disadvantage of linked lists is access time
to individual elements. Array is random-access, which means it takes 0(1) to access any element
in the array. Linked lists takes 0(n) for access to an element in the list in the worst case. Another
advantage of arrays in access time is special locality in memory. Arrays are defined as contiguous
blocks of memory, and so any array element will be physically near its neighbors. This greatly
benefits from modern CPU caching methods. Although the dynamic allocation of storage is a

LOVELY PROFESSIONAL UNIVERSITY 93