Linked List Explained In Python

Linked List Implementation Using Python

In our 4th installment of the Data Structure & Algo Series, we will discuss Linked List.

An alternative to arrays in python — Not By Me😛

If you’re looking to brush up on your coding skills for a job interview, or if you want to learn more about Python data structures besides the usual dictionaries and lists, then you’ve come to the right place!

A linked list is a data structure with the following qualities —

1. Each item in a linked list is referred to as a Node.
2. Each node consists of two parts — Data & Next(pointer to the next node).
3. The last node in a linked list will always point to None.
4. It is the most efficient dynamic array — No beforehand memory allocation is required.

Linked List Node

Above is a representation of a Linked List Node. A node contains data & next. Next points to another node in the linked list. This is how a linked list can be better than arrays, as no beforehand memory needs to be allocated for future insertions as we do in an array.

I know, you must be thinking that —

Bro, linked list uses more space because of that one honking next pointer you keep talking about. — You

Yeah, that is one drawback of using a linked list. But, stay with me as I present some advantages and amazing python implementation down the article.

I know, you just want to start writing some fancy python code😉. As a starter to our main course — which is Python Linked List Class, allow me to give you a brief about this article and what it contains for python developers.

Most of the articles out there will only show you the basic implementation of a Linked List. But, I intend to deliver a whole new approach to creating object-oriented data structure implementations.

In this article, you will learn —

1. How the linked list is an improvement over arrays
2. What are the main linked list operations and their time complexity
3. Practical applications of a linked list
4. Python implementation of a linked list

Let’s get started.

Photo by Braden Collum on Unsplash

Linked List — An Alternative To Arrays

Before moving on to the linked list and its implementation, it is important to understand —

why not arrays?

Arrays are created by allocating a memory block even when there are no items stored in it. Once you start storing items in it, at some point it will be full and to add more items you have to reassign another memory block of the same size.

This can cause memory wastage in case the arrays are not completely filled. This is one major advantage you can get when using a linked list.

Accessing items in an array is of constant time complexity. But, inserting items to random indexes to an array is more complex compared to a linked list. It will require shifting items to successfully complete the insertion.

To summarize, here are the major disadvantages of an array —

1. Fixed-size — allocate memory even before using an array
2. Insertion — Inserting an item in a random position is a complex process

But Dynamic arrays are cool — you said this?🧐

Similar problems can occur with dynamic arrays. For example, one needs to define a fixed size to keep on reallocating memory in case the array grows. This can still cause memory wastage.

Linked list on the other side has the following advantages over an array —

1. It can expand in constant time
2. No memory wastage when expanding
3. Constant time for inserting items anywhere in the linked list

Linked List Operations

Like every data structure, we discussed in Data Structure & Algo Series linked list also has a set of operations defined on it. They are —

1. insert() — Inserts a node in a linked list, O(n)
2. delete() — Removes a node, O(n)
3. delete_list() — Removes all nodes from a linked list, O(1)
4. count() — Returns the number of nodes, O(1)
5. find(n) — Finds nth node in a linked list, O(n)

Time complexities mentioned above, are for the worst cases. For example, insertion happening at the end of a linked list will take O(n).

Practical applications of a linked list

Before jumping to the code, let us quickly list out few cases where a linked list can be used. This idea will help you better decide when implementing a data structure.

1. Implementation of stacks and queues
2. Maintaining a directory of names
3. Image viewer — Previous and next images are linked
4. Dynamic memory allocation

Python implementation of a linked list

Now that you are aware of basic operations that can be performed on a linked list, it is time to see it in action. The code shown here will be also available on my GitHub page for your reference. I would suggest you follow along to have a deeper understanding of this code.

Without further ado, let’s implement our linked list class with all the operations as for instance methods as shown below —

Node and LinkedList Class

As in the example code above, there are two classes —

1. Node — Will be used to creating a new node which will contain data & next(pointer to the next node)
2. LinkedList — This is our main LinkedList class, that will be used to create a linked list and perform all main operations on it.

The advantage of implementing a data structure in this way is that you can even share this class with your peers so that can they also use it in their code.

This kind of code sharing is good

Now, let’s run this class and see it in action. I will create a linked list using our custom Linked List that we created above and perform some operations on it. The code is listed below —

The output will look something like this —

1
30
101
-9
22
=== Items after One Remove Operations ====
1
30
101
-9
==========================================
2nd item in the LinkedList is ::30

If you do not see this output, comment on this article so that I can help you resolve the issue in the code.

Also, here is the GitHub link of this source code for your reference — Data Structure.

So, it was a hell of a ride implementing a Linked List. I enjoyed it, not sure about you. If you want more articles on Data Structures uses the comment section. That is the best way you can reach out to me.

Coming Up Next

The next articles that I am planning are —

1. Implementing Tree In Python, in Data Structures & Algo Series.
2. Introduction to AWS Step Functions Using CDK and Python

Follow me for more👍.

More About The Author😄

I am a full-time software engineer with 4+ years of experience in Python, AWS, and many more technologies. I have started writing recently as it helps me to read more. I am looking forward to sharing technical knowledge and my life experiences with people out there.

• Github — https://github.com/varun-singh-01
• LinkedIn — https://www.linkedin.com/in/varun-singh-a02b2b118/
• Twitter — https://twitter.com/varunsh89
• Follow for more interesting articles — TalkHash