Lists questions

Topics

• Lists
• Stacks and queues

Lists

Write a recursive function to delete all the occurrences of a given key key in a singly-linked list and return the head of the new list. The function should have the prototype

ListNode *deleteOccurrences(ListNode *head, int key);

Answer.

Write a function to insert an element onto the front of a doubly linked list of nodes with the following type definition.

    struct ListNode {
        int             data;
        ListNode        *next; // pointer to next elt in list
        ListNode        *prev; // pointer to previous elt in list
    };

Answer.

Stacks and queues

In class and in Assignments 2 and 5 you implemented a queue using a linked list. Arrays allow a more efficient method for bounded-length queues. In an array, one has two indices indicating where the top and bottom of the queue are. When the index goes over the array bound, then we circle back 0 and begin again. Implement an array queue using the following class definition.

    class Queue {
    public:
                        Queue(int max_size);
                        ~Queue() { delete[] data; }
        int             isEmpty() { return counter == 0; }
        int             isFull() { return counter == max_size; }
        void            put(int item);
        int             get(); // return -1 if queue empty
    private:
        int             max_size;
        int             *data; // an array of length max_size
        int             head; // the index of the front item in queue
        int             tail; // the index of the end item in queue
        int             count; // the number of items in queue
    };

Answer.