|
|
|
|
|
|
|
more pointers to nodes of the same type. The pointer to the first node is saved in a variable called the external pointer to the structure. |
|
|
|
|
|
|
|
|
A linked list is a data structure in which the components are logically next to each other rather than physically next to each other as they are in an array. A linked list can be represented either as an array of structs or as a collection of dynamic nodes, linked together by pointers. The end of a dynamic linked list is indicated by the special pointer constant NULL. Common operations on linked lists include inserting a node, deleting a node, and traversing the list (visiting each node from first to last). |
|
|
|
|
|
|
|
|
In this chapter, we used linked lists to implement lists. But linked lists are also used to implement many data structures other than lists. The study of data structures forms a major topic in computer science. Entire books and courses are developed to cover the subject. A solid understanding of the fundamentals of linked lists is a prerequisite to creating more complex structures. |
|
|
|
|
|
|
|
|
1. What distinguishes a linked list from an array? (pp. 10461047) |
|
|
|
|
|
|
|
|
2. Nodes in a linked list structure must contain a link member. (True or False?) (pp. 10501052) |
|
|
|
|
|
|
|
|
3. The number of elements in a dynamic data structure must be determined before the program is compiled. (True or False?) (pp. 10501051) |
|
|
|
|
|
|
|
|
4. When printing the contents of a dynamically allocated linked list, what operation advances the current node pointer to the next node? (pp. 10631065) |
|
|
|
|
|
|
|
|
5. What is the difference between the operations of inserting a new item at the top of a linked list, and inserting the new item into its proper position in an ordered list? (pp. 10651074) |
|
|
|
|
|
|
|
|
6. In deleting an item from a linked list, why do we need to keep track of the previous node (the node before the one to be deleted)? (pp. 10741078) |
|
|
|
|
|
|
|
|
Answers 1. Arrays are data structures whose components are located next to each other in memory. Linked lists are data structures in which the locations of the components are defined by an explicit link member in each node. 2. True; every node (except the first) is accessed by using the link member in the node before it. 3. False; we do not have to know in advance how large it has to be. (In fact, we rarely know.) The only limitation is the amount of memory space available on the free store. 4. The current node pointer is set equal to the link member of the current node. 5. When inserting an item into position, the list must first be searched to find the proper place. We don't have to search the list when inserting at the top. 6. Because we must set the link member of the previous node equal to the link member of the current node as part of the deletion operation. |
|
|
|
|
|
|
|
|
Exam Preparation Exercises |
|
|
|
|
|
|
|
|
1. Given the OrdList class of this chapter and a client's declaration |
|
|
|
 |
|
|
|
|
OrdList myList; |
|
|
|
|
|
|
|
|
what is the output of each of the following code segments? |
|
|
|
|
|