Page 137 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Fundamentals of Data Structures

Notes Self Assessment

Fill in the blanks:
11. The ......................... list is accessible through the node marked head.

12. If the list is empty (In case of circular list), head will be NULL, and in that case set count
=......................... .
13. When all the nodes are arranged in a circular fashion, the ......................... node of the list
will be the node next to the head node.
14. The only difference between inserting a node at the beginning and at the ending is that,
after inserting the new node we just need to update the ......................... .
15. The first node of a circular list can be ......................... by simply replacing the next field of
tail node with the next field of the first node.

8.4 Summary

Linked list is a collection of data item, where each item is stored in a structure (node).

The ListLength() function takes a linked list as input and counts the number of nodes in the
list.

When Inserting a Node in Singly Linked List at the Beginning, a new node is inserted
before the current head node.

Deleting the last node in Singly Linked List is a bit trickier than removing the first node,
because algorithm should find a node, which is previous to the tail first.
When Deleting an Intermediate Node in Singly Linked List, node to be removed is always
located between two nodes.
Deleting Singly Linked List works by storing the current node in some temporary variable
and freeing the current node.
The circular list is accessible through the node marked head.

The only difference between inserting a node at the beginning and at the ending of a
circular linked list is that, after inserting the new node we just need to update the pointer.

8.5 Keywords

Circular Linked List: A circular linked list is a linked list in which the head element's previous
pointer points to the tail element and the tail element's next pointer points to the head element.
Doubly Linked List: A doubly linked list, in computer science, is a linked data structure that
consists of a set of sequentially linked records called nodes.
Linked List: Linked list is a collection of data item, where each item is stored in a structure
(node).

ListLength(): The ListLength() function takes a linked list as input and counts the number of
nodes in the list.

130 LOVELY PROFESSIONAL UNIVERSITY