Page 123 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Fundamentals of Data Structures

Notes Self Assessment

Fill in the blanks:
1. The .................... function takes a linked list as input and counts the number of nodes in the
list.

2. When Inserting a Node in Singly Linked List at the ...................., a new node is inserted
before the current head node.
3. Deleting the .................... 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.
4. When Deleting an .................... Node in Singly Linked List, node to be removed is always
located between two nodes.

5. Deleting Singly Linked List works by storing the .................... node in some temporary
variable and freeing the current node.

8.2 Basic Operations on Doubly Linked Lists

The Basic Operations on Doubly Linked Lists are discussed below:

8.2.1 Doubly Linked List Insertion

Insertion into a doubly-linked list has three cases (same as singly linked list):

Inserting a new node before the head.
Inserting a new node after the tail (at the end of the list).
Inserting a new node at the middle of the list.

Inserting a Node in Doubly Linked List at the Beginning

In this case, new node is inserted before the head node. Previous and next pointers need to be
modified and it can be done in two steps.

Example: The example given below shows the steps for inserting a Node in Doubly
Linked List at the Beginning.

Update the right pointer of new node to point to the current head node and also make left
pointer of new node as NULL.

!

Caution The current head node is shown by the dotted link in the figure given below:
Figure 8.13: Update the Right Pointer of New Node

Source: http://www.csie.ntu.edu.tw/~hsinmu/courses/lib/exe/fetch.php?media=dsa_12spring:
dsame_chap3.pdf

116 LOVELY PROFESSIONAL UNIVERSITY