In today's lecture we will continue to explore linked lists and will examine a number of useful "advanced" linked list operations that will round out our linked list toolkit.
- Readings: Text 14.2 - 14.4
- Lecture quiz on Canvas
Contents
1. Tail Pointers
2. Maintaining a Tail Pointer: Runtime Implications
3. Doubly-Linked Lists
4. Implementing Stacks and Queues with Linked Lists
5. Head Insertion and Deletion While Maintaining Tail Pointers
6. LinkedQueue
7. Member Functions with const
8. What's next?
9. Exercises
Tail Pointers
After a brief review of some basic linked list terminology, we talked about runtimes for inserting elements at the head and tail of a linked list.
As we saw last time, head insertion is an O(1) operation. Regardless of how long our linked list is, adding a new element to the beginning of our list is simply a matter of creating a new node, setting its next pointer to the old head of our linked list, and setting the head to point to our newly created node. All of that can be done in O(1) time.
The tail insertion function we saw last time had a linear runtime, but today we explored an idea for speeding that up: maintaining a pointer not just to the head of a linked list, but also to the tail! If we do that, we can achieve O(1) insertion at the tail of our list: we just set the tail's next pointer to a new node, then move the tail pointer forward. Voila! This is a ✨dramatic✨ improvement in runtime, and it only costs us two things: (1) the memory associated with maintaining a tail pointer (typically just 8 bytes in C++) and (2) the complexity and effort associated with writing code that correctly keeps track of the tail pointer.
Maintaining a tail pointer actually even makes our head insertion function more complex. That's because if we pass an empty list to our head insertion function, the new node we create will not only be the first node in the list, but also the last. If we have just one node in our list, it's both the head and the tail -- and so we need our head insertion function to be able to update both our head and tail pointers. (The code for this is included in the notes below, but before we got to coding those functions up in class, we continued with our conceptual exploration of these topics.)
Maintaining a Tail Pointer: Runtime Implications
We then reviewed the runtimes associated with insertion and deletion at both the head and tail of a linked list.
Note that if someone asked what the runtime is for insertion at the tail of a linked list, a precise answer would be to say, "It depends. If we maintain a tail pointer, we can do that in O(1) time. If not, it takes O(n) time."
Note that deletion at the tail of a linked list is O(n), even if we maintain a pointer to the tail of the list. With a tail pointer, we could certainly delete the dynamically allocated tail node in O(1) time, but we would then have to move the tail pointer back by one node in order to keep that pointer current -- and we can't do that in a traditional linked list. We have to start at the beginning of the list and loop forward until we find that next-to-last node, which will take O(n) time.
A common proposal I hear to get around that is to simply maintain a pointer to the next-to-last node, as well. That way, if we delete the tail, we can just set the tail pointer equal to our next-to-last pointer. The problem with this proposal is that the next-to-last pointer needs to move back, as well -- and unless we have a whole series of pointers that give us direct access to each node as we move backward through the list, this just isn't going to work out for us.
To summarize:
| insertion | deletion | |
|---|---|---|
| head | O(1) | O(1) |
| tail | O(1) if tail pointer O(n) otherwise |
O(1) if tail pointer and doubly-linked O(n) otherwise |
Doubly-Linked Lists
One way to implement an efficient tail deletion (which requires not only maintaining a tail pointer, but also being able to efficiently move that tail pointer back by one node in the list) is to maintain what we call a "doubly-linked list:" that is, a list in which every node has not only a next pointer, but a previous pointer, as well. That looks something like this:
seansz ~/Desktop $ ./a.out 87 93 12 --doubly-linked
addr: 0xf9800 0xf4d33 0xc625e
+---------+ +---------+ +---------+
data: | 87 | | 93 | | 12 |
+---------+ ---> +---------+ ---> +---------+
next: | 0xf4d33 | | 0xc625e | | nullptr |
+---------+ <--- +---------+ <--- +---------+
prev: | nullptr | | 0xf9800 | | 0xf4d33 |
+---------+ +---------+ +---------+
^
head = 0xf9800
seansz ~/Desktop $ _
The upside to doubly linked lists is that we can now achieve O(1) insertion and deletion at the tail of a linked list (provided we have a tail pointer). The downsides are that (1) every node now has an extra pointer (typically 8 bytes in C++), which means each node is up to 20 bytes of memory instead of just 12 (assuming each node also holds a 4-byte integer) -- a 67% increase in space complexity; and (2) all of our functions for inserting, moving, and deleting nodes in our linked lists become appreciably more complex if we have to maintain previous pointers.
(Key take-away!) This is part of a classical trade-off we see frequently in computer science: by using more memory, we can sometimes dramatically improve the runtimes of certain operations.
Implementing Stacks and Queues with Linked Lists
We then talked about how we would use linked lists to implement stacks and queues, with a focus on where we would perform our push and pop operations for the stack and our enqueue and dequeue operations for the queue. See timestamps 23:00 through 28:10 in today's lecture for details.
We saw that to implement a stack using a linked list, we would need to push and pop at the same end of our linked list. We can implement those operations efficiently if we always push and pop at the head of our list. As we discussed above, those are O(1) operations. (Popping at the tail would be an O(n) operation even with a tail pointer -- unless we grappled with the added complexity and memory usage of doubly-linked lists.)
To implement a queue using a linked list, we would need to enqueue and dequeue at opposite ends of our linked list. We want to avoid tail deletion for the reasons given above, so we would dequeue at the head (an O(1) operation) and enqueue at the tail (also an O(1) operation, provided that we maintain a tail pointer).
Head Insertion and Deletion While Maintaining Tail Pointers
Our updated head insertion function is as follows (and we also switched to using a constructor function without our struct, rather than a separate createNode() function). As we worked on these functions in class, I also took some additional time to talk about passing our pointers by reference. (See timestamps 28:55 through 30:05 in today's lecture. For a more detailed explanation, see the section of notes titled "Preliminary Note: Passing Pointers by Reference" from our first lecture on linked lists this past Wednesday.)
#include <iostream>
#include "console.h"
#include "error.h"
using namespace std;
struct Node
{
int data;
Node *next; // a pointer to a Node -- the next node in our list
Node(int d)
{
data = d;
next = nullptr;
}
};
// Insert a new node at the head of the list.
void headInsert(Node *&head, Node *&tail, int data)
{
Node *newNode = new Node(data);
newNode->next = head;
head = newNode;
// If tail is null and we have been keeping both our head and tail pointers up
// to date, that means the node we just inserted is the only node currently in
// the list -- making it both the head and the tail. We update the tail pointer
// accordingly.
if (tail == nullptr)
{
tail = head;
}
}
// Removes head of linked list and returns the value it contained.
int offWithItsHead(Node *&head, Node *&tail)
{
if (head == nullptr)
{
error("Empty list in offWithItsHead().");
}
// Let's hold onto our return value before deleting the head.
// "retval" stands for "return value."
int retval = head->data;
// Let's hold onto the head node we'll be deleting.
Node *temp = head;
// Move our head pointer forward.
head = head->next;
// If moving our head pointer forward caused it to fall off the end of the list,
// that means the list is now empty. We need to update the tail pointer in this
// case to reflect that.
if (head == nullptr)
{
tail = nullptr;
}
// BYE.
delete temp;
return retval;
}
int main()
{
// I cannot stress enough how important it is to initialize these both to nullptr.
Node *head = nullptr;
Node *tail = nullptr;
headInsert(head, tail, 10);
headInsert(head, tail, 12);
headInsert(head, tail, 15);
while (head != nullptr)
{
cout << offWithItsHead(head, tail) << endl;
}
cout << endl << "Pointers (should be 0 for nullptr):" << endl;
cout << head << endl;
cout << tail << endl;
return 0;
}
output:
15
12
10
Pointers (should be 0 for nullptr):
0
0
LinkedQueue
At the end of class, we implemented a queue using linked lists. As discussed above, the efficient implementation is to enqueue at the tail of the list (with a tail pointer) and to dequeue at the head. Our code was as follows:
node.h:
#ifndef NODE_H
#define NODE_H
struct Node
{
int data;
Node *next;
Node(int d)
{
data = d;
next = nullptr;
}
};
#endif // NODE_H
linkedqueue.h:
#ifndef LINKEDQUEUE_H
#define LINKEDQUEUE_H
#include "node.h" // for Node struct used in private fields
class LinkedQueue
{
public:
LinkedQueue();
~LinkedQueue();
void enqueue(int data);
int dequeue();
int peek() const;
int size() const;
bool isEmpty() const;
private:
Node *_head;
Node *_tail;
int _size;
};
#endif // LINKEDQUEUE_H
linkedqueue.cpp
#include "linkedqueue.h"
#include "node.h"
#include "error.h"
using namespace std;
LinkedQueue::LinkedQueue()
{
_head = nullptr;
_tail = nullptr;
_size = 0;
}
LinkedQueue::~LinkedQueue()
{
// WARNING!
// This has a memory leak! We aren't freeing the list in our destructor function.
}
void LinkedQueue::enqueue(int data)
{
_size++;
if (_tail == nullptr)
{
_tail = _head = new Node(data);
return;
}
_tail->next = new Node(data);
_tail = _tail->next;
}
int LinkedQueue::dequeue()
{
if (_head == nullptr)
{
error("Empty list in dequeue()!");
}
int retval = _head->data;
Node *temp = _head;
_head = _head->next;
if (_head == nullptr)
{
_tail = nullptr;
}
delete temp;
--_size;
return retval;
}
int LinkedQueue::peek() const
{
if (_head == nullptr)
{
error("Empty list in peek()!");
}
return _head->data;
}
int LinkedQueue::size() const
{
return _size;
}
bool LinkedQueue::isEmpty() const
{
return _head == nullptr;
}
main.cpp:
#include <iostream>
#include "console.h"
#include "linkedqueue.h"
using namespace std;
int main()
{
LinkedQueue q;
q.enqueue(10);
q.enqueue(15);
q.enqueue(20);
q.enqueue(12);
while (!q.isEmpty())
{
cout << q.dequeue() << endl;
cout << "New size: " << q.size() << endl;
}
return 0;
}
output:
10
New size: 3
15
New size: 2
20
New size: 1
12
New size: 0
Member Functions with const
This has come up in section already, but I also mentioned it in class today: If we have a member function in some class that we don't want to be able to modify any of our member variables, we can put const at the end of its declaration in our .h file, as with the peek(), size(), and isEmpty() functions above. If we try to modify one of our member variables inside one of those functions, our compiler will actually give us an error now. This is are really neat way to protect ourselves from accidentally modifying a member variable in a function where we're not supposed to do that.
What's next?
On Monday, we'll dive into a new linked data structure: binary trees!
Exercises
1. As always, after reviewing today's lecture materials, challenge yourself to reproduce all of today's code from scratch without referring back to the notes for assistance. The key to getting good at linked lists (and working with pointers in general) is to engage in lots of coding practice.
2. Write an tailDelete() function that maintains both a head and tail pointer. The function signature is:
int tailInsert(Node *&head, Node *&tail)
3. Write head and tail insertion and deletion functions that operate on doubly linked lists. Maintain both head and tail pointers.
4. Write an O(n) destructor function for our LinkedQueue class that clears up all the dynamically allocated nodes remaining in the queue.
5. Continue working on your current linked lists assignment.
6. Friendly reminder: Your final exam will involve writing some fairly complex code on paper. Don't forget to detach from the Qt Creator every now and then and do a bit of coding and debugging practice on paper so that you're ultra-prepared for that when you get into the exam. It's not too early to start preparing.