Queues or Stacks

Queues and stacks differ only in the way elements are retrieved. For a queue, you use aFirst-In/First-Out (FIFO) approach. That means that the first element inserted in the list is the first one to be retrieved:

In the diagram above, you can see thefront andrear elements of the queue. When you append new elements to the queue, they’ll go to the rear end. When you retrieve elements, they’ll be taken from the front of the queue.

For a stack, you use aLast-In/First-Out (LIFO) approach, meaning that the last element inserted in the list is the first to be retrieved:

In the above diagram you can see that the first element inserted on the stack (index0) is at the bottom, and the last element inserted is at the top. Since stacks use the LIFO approach, the last element inserted (at the top) will be the first to be retrieved.

Because of the way you insert and retrieve elements from the edges of queues and stacks, linked lists are one of the most convenient ways to implement these data structures. You’ll see examples of these implementations later in the article.

Graphs

Graphs can be used to show relationships between objects or to represent different types of networks. For example, a visual representation of a graph—say a directed acyclic graph (DAG)—might look like this:

There are different ways to implement graphs like the above, but one of the most common is to use anadjacency list. An adjacency list is, in essence, a list of linked lists where each vertex of the graph is stored alongside a collection of connected vertices:

In the table above, each vertex of your graph is listed in the left column. The right column contains a series of linked lists storing the other vertices connected with the corresponding vertex in the left column. This adjacency list could also be represented in code using adict:

>>>graph={...1:[2,3,None],...2:[4,None],...3:[None],...4:[5,6,None],...5:[6,None],...6:[None]...}

The keys of this dictionary are the source vertices, and the value for each key is a list. This list is usually implemented as a linked list.

In terms of both speed and memory, implementing graphs using adjacency lists is very efficient in comparison with, for example, anadjacency matrix. That’s why linked lists are so useful for graph implementation.

Insertion and Deletion of Elements

In Python, you can insert elements into a list using.insert() or.append(). For removing elements from a list, you can use their counterparts:.remove() and.pop().

The main difference between these methods is that you use.insert() and.remove() to insert or remove elements at a specific position in a list, but you use.append() and.pop() only to insert or remove elements at the end of a list.

Now, something you need to know about Python lists is that inserting or removing elements that arenot at the end of the list requires some element shifting in the background, making the operation more complex in terms of time spent. You can read the article mentioned above onhow lists are implemented in Python to better understand how the implementation of.insert(),.remove(),.append() and.pop() affects their performance.

With all this in mind, even though inserting elements at the end of a list using.append() or.insert() will have constant time,O(1), when you try inserting an element closer to or at the beginning of the list, the average time complexity will grow along with the size of the list:O(n).

Linked lists, on the other hand, are much more straightforward when it comes to insertion and deletion of elements at the beginning or end of a list, where their time complexity is always constant:O(1).

For this reason, linked lists have a performance advantage over normal lists when implementing a queue (FIFO), in which elements are continuously inserted and removed at the beginning of the list. But they perform similarly to a list when implementing a stack (LIFO), in which elements are inserted and removed at the end of the list.

Retrieval of Elements

When it comes to element lookup, lists perform much better than linked lists. When you know which element you want to access, lists can perform this operation inO(1) time. Trying to do the same with a linked list would takeO(n) because you need to traverse the whole list to find the element.

When searching for a specific element, however, both lists and linked lists perform very similarly, with a time complexity ofO(n). In both cases, you need to iterate through the entire list to find the element you’re looking for.

Queues

With queues, you want to add values to a list (enqueue), and when the timing is right, you want to remove the element that has been on the list the longest (dequeue). For example, imagine a queue at a trendy and fully booked restaurant. If you were trying to implement a fair system for seating guests, then you’d start by creating a queue and adding people as they arrive:

>>>fromcollectionsimportdeque>>>queue=deque()>>>queuedeque([])>>>queue.append("Mary")>>>queue.append("John")>>>queue.append("Susan")>>>queuedeque(['Mary', 'John', 'Susan'])

Now you have Mary, John, and Susan in the queue. Remember that since queues are FIFO, the first person who got into the queue should be the first to get out.

Now imagine some time goes by and a few tables become available. At this stage, you want to remove people from the queue in the correct order. This is how you would do that:

>>>queue.popleft()'Mary'>>>queuedeque(['John', 'Susan'])>>>queue.popleft()'John'>>>queuedeque(['Susan'])

Every time you callpopleft(), you remove the head element from the linked list, mimicking a real-life queue.

Stacks

What if you wanted tocreate a stack instead? Well, the idea is more or less the same as with the queue. The only difference is that the stack uses the LIFO approach, meaning that the last element to be inserted in the stack should be the first to be removed.

Imagine you’re creating a web browser’s history functionality in which store every page a user visits so they can go back in time easily. Assume these are the actions a random user takes on their browser:

1. VisitsReal Python’s website
2. Navigates toPandas: How to Read and Write Files
3. Clicks on a link forReading and Writing CSV Files in Python

If you’d like to map this behavior into a stack, then you could do something like this:

>>>fromcollectionsimportdeque>>>history=deque()>>>history.appendleft("https://realpython.com/")>>>history.appendleft("https://realpython.com/pandas-read-write-files/")>>>history.appendleft("https://realpython.com/python-csv/")>>>historydeque(['https://realpython.com/python-csv/',       'https://realpython.com/pandas-read-write-files/',       'https://realpython.com/'])

In this example, you created an emptyhistory object, and every time the user visited a new site, you added it to yourhistory variable usingappendleft(). Doing so ensured that each new element was added to thehead of the linked list.

Now suppose that after the user read both articles, they wanted to go back to the Real Python home page to pick a new article to read. Knowing that you have a stack and want to remove elements using LIFO, you could do the following:

>>>history.popleft()'https://realpython.com/python-csv/'>>>history.popleft()'https://realpython.com/pandas-read-write-files/'>>>historydeque(['https://realpython.com/'])

There you go! Usingpopleft(), you removed elements from thehead of the linked list until you reached the Real Python home page.

From the examples above, you can see how useful it can be to havecollections.deque in your toolbox, so make sure to use it the next time you have a queue- or stack-based challenge to solve.

Inserting at the Beginning

Inserting a new node at the beginning of a list is probably the most straightforward insertion since you don’t have to traverse the whole list to do it. It’s all about creating a new node and then pointing thehead of the list to it.

Have a look at the following implementation ofadd_first() for the classLinkedList:

defadd_first(self,node):node.next=self.headself.head=node

In the above example, you’re settingself.head as thenext reference of the new node so that the new node points to the oldself.head. After that, you need to state that the newhead of the list is the inserted node.

Here’s how it behaves with a sample list:

>>>llist=LinkedList()>>>llistNone>>>llist.add_first(Node("b"))>>>llistb -> None>>>llist.add_first(Node("a"))>>>llista -> b -> None

As you can see,add_first() always adds the node to thehead of the list, even if the list was empty before.

Inserting at the End

Inserting a new node at the end of the list forces you to traverse the whole linked list first and to add the new node when you reach the end. You can’t just append to the end as you would with a normal list because in a linked list you don’t know which node is last.

Here’s an example implementation of a function for inserting a node to the end of a linked list:

defadd_last(self,node):ifself.headisNone:self.head=nodereturnforcurrent_nodeinself:passcurrent_node.next=node

First, you want to traverse the whole list until you reach the end (that is, until thefor loop raises aStopIteration exception). Next, you want to set thecurrent_node as the last node on the list. Finally, you want to add the new node as thenext value of thatcurrent_node.

Here’s an example ofadd_last() in action:

>>>llist=LinkedList(["a","b","c","d"])>>>llista -> b -> c -> d -> None>>>llist.add_last(Node("e"))>>>llista -> b -> c -> d -> e -> None>>>llist.add_last(Node("f"))>>>llista -> b -> c -> d -> e -> f -> None

In the code above, you start by creating a list with four values (a,b,c, andd). Then, when you add new nodes usingadd_last(), you can see that the nodes are always appended to the end of the list.

Inserting Between Two Nodes

Inserting between two nodes adds yet another layer of complexity to the linked list’s already complex insertions because there are two different approaches that you can use:

1. Insertingafter an existing node
2. Insertingbefore an existing node

It might seem weird to split these into two methods, but linked lists behave differently than normal lists, and you need a different implementation for each case.

Here’s a method that adds a nodeafter an existing node with a specific data value:

defadd_after(self,target_node_data,new_node):ifself.headisNone:raiseException("List is empty")fornodeinself:ifnode.data==target_node_data:new_node.next=node.nextnode.next=new_nodereturnraiseException("Node with data '%s' not found"%target_node_data)

In the above code, you’re traversing the linked list looking for the node with data indicating where you want to insert a new node. When you find the node you’re looking for, you’ll insert the new node immediately after it and rewire thenext reference to maintain the consistency of the list.

The only exceptions are if the list is empty, making it impossible to insert a new node after an existing node, or if the list does not contain the value you’re searching for. Here are a few examples of howadd_after() behaves:

>>>llist=LinkedList()>>>llist.add_after("a",Node("b"))Exception: List is empty>>>llist=LinkedList(["a","b","c","d"])>>>llista -> b -> c -> d -> None>>>llist.add_after("c",Node("cc"))>>>llista -> b -> c -> cc -> d -> None>>>llist.add_after("f",Node("g"))Exception: Node with data 'f' not found

Trying to useadd_after() on an empty list results in anexception. The same happens when you try to add after a nonexistent node. Everything else works as expected.

Now, if you want to implementadd_before(), then it will look something like this:

 1defadd_before(self,target_node_data,new_node): 2ifself.headisNone: 3raiseException("List is empty") 4 5ifself.head.data==target_node_data: 6returnself.add_first(new_node) 7 8prev_node=self.head 9fornodeinself:10ifnode.data==target_node_data:11prev_node.next=new_node12new_node.next=node13return14prev_node=node1516raiseException("Node with data '%s' not found"%target_node_data)

There are a few things to keep in mind while implementing the above. First, as withadd_after(), you want to make sure to raise an exception if the linked list is empty (line 2) or the node you’re looking for is not present (line 16).

Second, if you’re trying to add a new node before the head of the list (line 5), then you can reuseadd_first() because the node you’re inserting will be the newhead of the list.

Finally, for any other case (line 9), you should keep track of the last-checked node using theprev_node variable. Then, when you find the target node, you can use thatprev_node variable to rewire thenext values.

Once again, an example is worth a thousand words:

>>>llist=LinkedList()>>>llist.add_before("a",Node("a"))Exception: List is empty>>>llist=LinkedList(["b","c"])>>>llistb -> c -> None>>>llist.add_before("b",Node("a"))>>>llista -> b -> c -> None>>>llist.add_before("b",Node("aa"))>>>llist.add_before("c",Node("bb"))>>>llista -> aa -> b -> bb -> c -> None>>>llist.add_before("n",Node("m"))Exception: Node with data 'n' not found

Withadd_before(), you now have all the methods you need to insert nodes anywhere you’d like in your list.