Applications: Stacks, Queues, and Graphs
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: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.
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: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.
Become a Member to join the conversation.