(a) Linked Lists: (i) Declare a struct to represent a node in a linked list. The
ID: 3691510 • Letter: #
Question
(a) Linked Lists:
(i) Declare a struct to represent a node in a linked list. The node should have an integer datum field and a pointer to the next node.
(ii) Declare a variable to keep track of a linked list.
(iii) Write a function that (a) creates a node and stores the integer value x in it and (b) adds this node to the end of a linked list. The parameters are a pointer to the head of the linked list and x. (Note for 201610 term: no tail pointer is available!)
(iv) Write a function that creates a copy of a linked list that is in reversed order. The original linked list should not be changed and its nodes should not be reused in the reversed list. The only parameter is a pointer to the head of the original linked list and the returned value is a pointer to the head of the reversed list.
Explanation / Answer
(i) Declare a struct to represent a node in a linked list. The node should have an integer datum field and a pointer to the next node.
Designing the Node
Linked list is a collection of linked nodes. A node is a struct with at least a data field and a reference to a node of the same type. A node is called a self-referential object, since it contains a pointer to a variable that refers to a variable of the same type. For example, a struct Node that contains an int data field and a pointer to another node can be defined as follows.
struct Node {
int data;
struct Node* next;
}
typedef struct Node node;
node* head = NULL;
Allocating memory for the first node
Memory must be allocated for one node and assigned to head as follows.
head = (node*) malloc(sizeof(node));
(*head).data = 10;
(*head).next = NULL;
Adding the second node and linking
node* nextnode = malloc(sizeof(node));
(*nextnode).data = 12;
(*nextnode).next = NULL;
(*head).next = nextnode;
(ii) Declare a variable to keep track of a linked list.
Singly linked lists
Our node data structure will have two fields. We also keep a variable firstNode which always points to the first node in the list, or is null for an empty list.
Traversal of a singly linked list is simple, beginning at the first node and following each next link until we come to the end:
iii) Write a function that (a) creates a node and stores the integer value x in it and (b) adds this node to the end of a linked list. The parameters are a pointer to the head of the linked list and x. (Note for 201610 term: no tail pointer is available!)
(iv) Write a function that creates a copy of a linked list that is in reversed order. The original linked list should not be changed and its nodes should not be reused in the reversed list. The only parameter is a pointer to the head of the original linked list and the returned value is a pointer to the head of the reversed list.
One way of reversing the list involves passing back the new head of the list once we find it. We don't need it locally (since we're just moving the current element to the new end), but we'll need it so that the caller has a pointer to the head of the list once we're done.
Another way takes a pointer to a pointer. The only difference is that we don't need to return anything, since we're directly modifying a variable the caller has. I prefer this calling method since it's much clearer that we're modifying the list, not returning a copy. It's also harder for the caller to accidentally loose the pointer to the new head this way.
But what's better than either of these is to reverse the list non-recursively. Neither of those functions is tail-recursive, so the compiler has to allocate new stack frames for each element in the list. Try to reverse a long enough list, and you'll blow your stack. Much better to just reverse the list using a while loop.
Now we can test our results just by building lists out of the command line:
So let's compile:
And do some test runs
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.