tailieunhanh - Lecture Data structures and other objects using C++ - Chapter 5: Linked lists in action

This lecture shows three linked list operation in detail. The operations are: Adding a new node at the head of a linked list, adding a new node in the middle of a linked list, removing a node from a linked list. The best time for this lecture is just after the students have been introduced to linked lists, and before the complete linked list toolkit has been covered. | Chapter 5 introduces the often-used data structure of linked lists. This presentation shows how to implement the most common operations on linked lists. Linked Lists in Action CHAPTER 5 Data Structures and Other Objects This lecture shows three linked list operation in detail. The operations are: 1. Adding a new node at the head of a linked list. 2. Adding a new node in the middle of a linked list. 3. Removing a node from a linked list. The best time for this lecture is just after the students have been introduced to linked lists (Section ), and before the complete linked list toolkit has been covered (Section ). For this presentation, nodes in a linked list are objects, as shown here. data_field link_field 10 data_field link_field 15 data_field link_field 7 null class node { public: typedef double value_type; . private value_type data_field; node *link_field; }; Declarations for Linked Lists Here is a typical class declaration that can be used to implement a linked list of integers, as described in Section of the text. Note that we have used a class rather than a struct. In a struct, the data and link members would typically be public, but there is more difficulty in ensuring that no part of a linked list is changed via a const pointer to a node. The data_field of each node is a type called value_type, defined by a typedef. data_field link_field 10 data_field link_field 15 data_field link_field 7 null class node { public: typedef int value_type; . private value_type data_field; node *link_field; }; Declarations for Linked Lists Within the node class, there is a type definition for a type called called "value_type". The purpose of the value_type is to tell us what kind of data resides in each of the nodes on the linked list. For example, if we want to create a linked list of real numbers, then we would declare typedef double Item; In this example, we want a linked list of integers, so we have declared typedef int value_type; As you can see, the . | Chapter 5 introduces the often-used data structure of linked lists. This presentation shows how to implement the most common operations on linked lists. Linked Lists in Action CHAPTER 5 Data Structures and Other Objects This lecture shows three linked list operation in detail. The operations are: 1. Adding a new node at the head of a linked list. 2. Adding a new node in the middle of a linked list. 3. Removing a node from a linked list. The best time for this lecture is just after the students have been introduced to linked lists (Section ), and before the complete linked list toolkit has been covered (Section ). For this presentation, nodes in a linked list are objects, as shown here. data_field link_field 10 data_field link_field 15 data_field link_field 7 null class node { public: typedef double value_type; . private value_type data_field; node *link_field; }; Declarations for Linked Lists Here is a typical class declaration that can be used to implement a linked list of .