Consider the material on linked lists that we discussed in the lecture with the following definition (Item is a char now):
typedef char Item; typedef struct node *link; struct node { Item item; link next; };
Write the following functions:
// Create a new node, initialised with the item provided. Return // pointer to node (link) link newNode (Item item); // Insert a new node into a given non-empty list // The node is inserted directly after the head of the list ls void insertNext (link ls, link node);
Assume we have a function printList which, given a list of characters, prints each character, and a function `cstrToList` which converts a regular C string (i.e., `\0` terminated array of characters) into a list of characters. What is the output of the following program? (See implementation of reverse in Exercise 2.)
int main (int argc, const char * argv[]) { link ls = cstrToList ("hello world!"); link ls2 = duplicate(ls); printList (ls); printList (ls2); printList (reverse (ls)); printList (ls); printList (ls2); return 0; }
typedef char Item; typedef struct node *link; struct node { Item item; link next; }; typedef struct listImpl *list; struct listImpl { int size; link first; link last; };
link reverse (link ls); void insertNext(link ls, link node); void deleteNext(link ls);
link reverse (link ls) { link tmp; link curr = ls; link rev = NULL; while (curr != NULL) { tmp = curr->next; curr->next = rev; rev = curr; curr = tmp; } return rev; }What are the advantages and disadvantages of your adapted version over the one discussed in the lecture? Which operations can be implemented more efficiently?
In the lecture, we briefly discussed doubly linked lists.
typedef char Item; typedef struct dnode *dlink; struct dnode { Item item; dlink next; dlink prev; };
Write a function
dlink append (dlink list1, dlink2 list2)
which attaches the list list2 at the end of list1 and returns the resulting list.
Is it necessary to return the resulting list, or would the following interface work (as list1 is altered)
void append (dlink list1, dlink list2)