Page 96 - DCAP407_DATA_STRUCTURE

Unit 5: Introduction to Linked List

5.4 Summary

• Linked list is a technique of dynamically implementing a list using pointers. A linked list contains
two fields namely, data field and link field.
• Linked lists are useful when the number of elements to be stored in a list is indefinite.
• The HEAD node or the START node depicts the beginning of the list and holds the total number of
elements or nodes present in a list. The various types of linked lists are singly-linked list, doubly-
linked list, circular singly-linked list, and circular doubly-linked list.
• A singly-linked list consists of only one pointer to point to another node and the last node always
points to NULL to indicate the end of the list.
• A doubly-linked list consists of two pointers, one to point to the next node and the other to point
to the previous node.

• In a circular singly-linked list, the last node always points to the first node to indicate the circular
nature of the list.
• A circular doubly-linked list consists of two pointers for forward and backward traversal and the
last node points to the first node.

• Except for circular linked list, all other types of linked lists assign a NULL value to the last node to
depict the end of the list
5.5 Keywords

Abstract Data Type (ADT): It is a mathematical model for certain classes of data structure such as, lists,
stacks, tress, graphs, and so on that are similar in behavior.
Iteration: In programming, iteration is an act of repeating a certain process to obtain the desired output.
Null Pointer: It is a pointer not pointing to any element in the list. The link field of the last node is
assigned a NULL value instead of any address.
Start Node: It is also known as an external pointer. A start node consists of the address of the first node.
Using the first node’s address the next consecutive nodes can be accessed.

5.6 Self Assessment
1. State whether the following statements are true or false:
(a) A linked list follows a strategy of allocating memory in a single block.
(b) The data field is a pointer that points to the data present in the consecutive nodes.

(c) The disadvantage of using arrays is its ability to store a fixed number of elements.
(d) A singly-linked list consists of a single pointer to point to the next node in the list.
(e) The HEAD node in a linked list can hold a dummy data or store the total nodes present in
the list.
2. Fill in the blanks:

(a) When there are no nodes present in a list, the list is known as ……………………….
(b) ………………………. consists of two pointers for each node in a list.
(c) In a ………………………. list does the last node’s pointer points to the head node.
(d) ……………. are useful when you are not clear of the number of elements to be stored in a list.

LOVELY PROFESSIONAL UNIVERSITY 89