Page 123 - DCAP407_DATA_STRUCTURE

Data Structure

Use of Singly-Linked Lists in Development of Processors

Technical Systems Consultants is a U.S. based software company, a supplier of software for Southwest
Technical Products Corporation (SWTPC). The operating systems developed by Technical Systems
Consultants used singly-linked lists as file structures, a directory entry pointed to the first sector of a
file, and succeeding portions of the file were located by traversing pointers. The systems that used this
technique are Flex (Motorola 6800 CPU), mini-Flex, and Flex9 (Motorola 6809 CPU).

Source: http://www.absoluteastronomy.com/topics/Linked_list

1. Write a program to delete a node at the end of a doubly-linked list. The
program should prompt users to enter the data and must contain three
functions create_node(), delete_end(), and display().
2. Write a program to insert a node at the beginning of a circular doubly-linked
list. The program should prompt users to enter the data and must contain
three functions create_node(), delete_end(), and display().

6.5 Summary
• We can perform many operations on a linked list like traversing, searching, inserting and deleting.

• The traversal operation in a linked list involves processing every node present in a list to obtain
the desired output.
• Searching operation involves searching for a specific element in the list using an associated key.
• Insertion operation involves inserting a node at the beginning or end of a list.

• Deletion operation involves deleting a node at the beginning or following a given node or at the
end of a list.
6.6 Keywords

Key Element: An element from a given list which is made as a base reference to search other elements in
that list.

Link Field: The initial word of a message buffer which is used to point to the next buffer on the message
row.
6.7 Self Assessment

1. State whether the following statements are true or false:
(a) It is possible to insert an element anywhere in the linked list.
(b) Linked list stores only a fixed set of data in the list.
(c) Traversing operation is used to search a specific element in the list.
(d) Deletion of a node can be done only at the beginning or end of a list.

(e) Search operation is used for reversing and sorting the list elements.

116 LOVELY PROFESSIONAL UNIVERSITY