Page 103 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Fundamentals of Data Structures

Notes LINK[10] = 4, so INFO[4] = T is the seventh character.
LINK[4] = 0, so the NULL value, so the list has ended.

Self Assessment

State whether the following statements are true or false:

1. A linked list is a collection of objects linked together by references from one object to
another object.
2. The first node points to a NULL reference to indicate the end of the list.

3. If the list is empty, then the head has the value NULL.
4. If the last item is deleted, the last but one must now have its pointer changed to hold a
NULL reference.

5. A node is a struct with at least a data field and a reference to a node of different types.
6. Linked list requires two linear arrays.

7.2 Types of Linked Lists

Linked lists are widely used in many applications because of the flexibility it provides. Unlike
arrays that are dynamically assigned, linked lists do not require memory from a contiguous
block. This makes it very appealing to store data in a linked list, when the data set is large or
device (e.g.: PDA) has limited memory. One of the disadvantages of linked lists is that they are
not random accessed like arrays. To find information in a linked list one must start from the
head of the list and traverse the list sequentially until it finds (or not find) the node. Another
advantage of linked lists over arrays is that when a node is inserted or deleted, there is no need
to “adjust” the array.
There are few different types of linked lists.

7.2.1 Singly Linked List

Generally “linked list” means a singly linked list. This list consists of a number of nodes in
which each node has a next pointer to the following element.

Did u know? The link of the last node in the list is NULL which indicates end of the list.
A singly linked list as described above provides access to the list from the head node. Traversal
is allowed only one way and there is no going back.

Figure 7.5: Singly Linked List

Let us write a C program that create a singly linked list.
/*c program for creating singly linked list*/
#include<stdio.h>

96 LOVELY PROFESSIONAL UNIVERSITY