1 #include "link2.h"
2 #include <assert.h>
3
list_length(Node * head_ptr)4 size_t list_length(Node* head_ptr)
5 // Precondition: head_ptr is the head pointer of a linked list
6 // Postcondition: the value returned is the number of nodes in the linked
7 // list
8 // The list itself is unaltered - libraries used: stdlib.h
9 {
10 Node* cursor;
11 size_t answer;
12
13 answer = 0;
14 for(cursor = head_ptr; cursor != NULL; cursor = cursor->link)
15 answer++;
16
17 return answer;
18 }
19
list_head_insert(Node * & head_ptr,const Node & entry)20 void list_head_insert(Node*& head_ptr, const Node& entry)
21 /* Precondition: head_ptr is the head pointer of a linked list.
22 Postcondition: a new node containing the given entry is added to the
23 head of the list
24 head_ptr now points to the head of the new, longer list
25 Note: if there is not enough dynamic memory for the new list, then
26 new_handler is called before changing the list
27
28 */
29
30 {
31 Node*insert_ptr;
32
33 insert_ptr = new Node;
34 insert_ptr->data = entry.data;
35 insert_ptr->link = head_ptr;
36 head_ptr = insert_ptr;
37 }
38
39
40
list_locate(Node * head_ptr,size_t position)41 Node* list_locate(Node* head_ptr, size_t position)
42 /* Precondition: head_ptr is the head pointer of a linked list and position
43 > 0
44 Postcondition: the pointer returned points to the node at the specified
45 position in the list. (the head node is poisiton 1. the next node is 2
46 and so on) If there is no such position then the null pointer is returned
47 and the list itself is undeclared.
48
49 Library facilities used: assert.h stdlib.h
50 */
51
52 {
53 Node *cursor;
54 size_t i;
55
56 assert(0<position);
57 cursor = head_ptr;
58 for(i = 1; (i<position) && (cursor != NULL); i++)
59 cursor = cursor->link;
60
61 return cursor;
62 }
63
list_copy(Node * source_ptr,Node * & head_ptr,Node * & tail_ptr)64 void list_copy(Node* source_ptr, Node*& head_ptr, Node*& tail_ptr)
65 /* Precondition: source_ptr is the head pointer of a linked list
66 Postcondition: head_ptr and tail_ptr are the head and tail pointers
67 for a new list that contains the same Cards as the list pointed to by
68 source_ptr. THe original list is unaltered. Note: if there is insufficient
69 dynamic memory to create the new list, then new_handler is called
70
71 Library facilities used: stdlib.h
72 */
73
74
75 {
76 head_ptr = NULL;
77 tail_ptr = NULL;
78
79 // Handle the case of the empty list.
80 if(source_ptr == NULL)
81 return;
82
83 // Make the head node for the newly created list, and put data into it
84 list_head_insert(head_ptr, *source_ptr);
85 tail_ptr = head_ptr;
86
87 //Copy the rest of the nodes one at a time, adding the tail of a new list
88 for(source_ptr = source_ptr->link; source_ptr!=NULL; source_ptr = source_ptr->link)
89 {
90 list_head_insert(tail_ptr, *source_ptr);
91 tail_ptr = tail_ptr->link;
92 }
93 }
94
95
96
list_head_remove(Node * & head_ptr)97 void list_head_remove(Node*& head_ptr)
98 /* Precondition: head_ptr is the head pointer of a linked list, with at least
99 one node
100 Postcondition: the head node has been removed and returned to the head
101 head_ptr is now the head pointer of the new, shorter linked list
102 */
103
104 {
105 Node *remove_ptr;
106
107 remove_ptr = head_ptr;
108 head_ptr = head_ptr -> link;
109 delete remove_ptr;
110 }
111
list_remove(Node * previous_ptr)112 void list_remove(Node* previous_ptr)
113 /* Precondition: previous_ptr points to a node in a linked list, and this is
114 not the tail node of the list.
115 Postcondition: the node after previous_ptr has been removed from the linked
116 list
117 */
118
119 {
120 Node *remove_ptr;
121
122 remove_ptr = previous_ptr->link;
123 previous_ptr->link = remove_ptr->link;
124 delete remove_ptr;
125 }
126
list_clear(Node * & head_ptr)127 void list_clear(Node*& head_ptr)
128 /* Precondition: head_ptr is the head pointer of a linked list
129 Postcondition: all nodes of the list have been returned to the heap, and
130 heap_ptr is now NULL
131
132 Library function used: stdlib.h
133 */
134
135 {
136 while(head_ptr != NULL)
137 list_head_remove(head_ptr);
138 }