Applications: Stacks, Queues, and Graphs

00:00 As you learned in the last video, linked lists are great for modeling data structures that require only access to the first and last elements in a collection. One example of this is a stack.

00:14 A stack is a data structure that models a real-world stack of objects. That is, you can place things on top of the stack and then remove them.

00:26 The only limitation is that you can only access the element at the top; you don’t have access to any element beneath that. If you want to access the next element from the top, you must first remove the top element.

00:41 This is called a Last In First Out structure, or LIFO, because the last item inserted is the first one that must be removed. Since the stack only deals with inserting, accessing, and removing elements at the very beginning of the collection, the linked list works great.

01:02 First, I’ll create a node that will live at the bottom of the stack. To add a new node, I just create it and point it to the previous head. This can be done as many times as we need with no performance penalties since insertion at the beginning of a linked list is a constant time operation.

01:23 I can’t access the middle or the bottom item in the stack in constant time because that would require traversal. To remove the top node, I can simply change the head pointer so that it points to its next node.

01:38 Now that the topmost node has nothing pointing to it, Python’s garbage collector will remove it from memory.

01:46 A queue is similar to a stack, except that it models a real-world queue. You can only insert new items at the rear of the queue, a process called queuing. You can only remove items from the front, a process called dequeuing.

02:04 Think about this like a line for a roller coaster. To enter the line, you must enter at the rear. To get to the roller coaster, you must exit at the front. Unlike the stack, which grows and shrinks from one end, the queue uses both ends to simulate movement in one direction.

02:24 This is known as First In First Out, or as I call it, FIFO.

02:31 Queues can be implemented with linked lists, too. The only thing that’s different is that you must also maintain a pointer to the node at the front of the queue.

02:41 This way, you can dequeue it when you need to.

02:46 Another data structure that often uses linked lists is the graph. Graphs show the relationships between connected entities, called vertices. This here is a directed acyclic graph.

03:00 It’s directed because each arrow points in only one direction, and it’s acyclic because there’s no way to traverse the elements in a cycle. 4 points at 5 and 5 points at 6, but 6 points at no other vertices. Graphs like this have many uses in

03:21 mathematics and computer science. There are a few ways you could implement the directed acyclic graph, but the most common is to use an adjacency list.

03:33 The adjacency list can be represented as a dictionary where the keys are the individual vertices and the values are linked lists that represent all the possible vertices you can travel to from the given vertex in one move.

03:51 For example, if I’m at vertex 1, I can travel to vertex 2 or 3 in a single move. Adjacency lists are very efficient in terms of speed and memory usage, and that’s due to the fact that they utilize linked lists under the hood.

04:09 In the next few videos, you’ll learn about a Python module that allows you to use and create linked lists.