LinkedList | Python | Basics to Advance

Why we should learn this?

We all know data structures and algorithms are the foundation of being a good software engineer.

Usually these foundation concepts are considered to be worthy only if you are in university or you are preparing for an interview for a big tech company.

But I have a different take on this. As an engineer you should be asking yourself this question: "As an engineer should I know X?" and if the answer is yes then please put some time in that topic to be a good engineer in general not because you are trying to score a job.

So, the questions is, as engineers - you think we should know the most basic but useful data structure called Linked-List?

I heard a big yes!!

So let's begin:

Definition and Dictionary

Linked list is a linear data structure.
Basically it contains only two things: data and next
This data can be anything, from just an int to an array or dictionary.
next is a pointer which points towards the next Node
Node is just a name we use for every linked entity in the linked list. Node is somewhat similar to what you have in array as an index.

So in simple words, linked list is collection of Nodes linked together with pointers.

Why this data structure even exists?

One may ask, we already have a linear data structure known as arrays then why we created a similar but new one? Why?

Then let me ask a question:
How do you add a new element in the middle of an array?

Find where you want to add new element.
Add new element
And shift the rest of the array one

Linked lists solve such issues like shifting the array after adding a new element in the middle.

Implementation

In python, it is really easy create some classes to reflect this data structure, like the code given below:

class LinkedList:
    def __init__(self, head=None):
        self.head = None

class Node:
    def __init__(self, data, next=None):
        self.data = data
        self.next = next

Creating from Array

You might be wondering how can you create this linked list and see it in action.
For this we can write a simple function to create a linked list from array and then visit every node of the linked list with another function.

def createFromArray(nodeList):

    ll = LinkedList()

    prev = None
    for n in nums:
        curr = Node(n)

        if not prev:
            ll.head = curr
        else:
            prev.next = curr

        prev = curr

    return ll

# Make linked-list from array - O(n)
nums = [1,2,3,4,5]
ll = createFromArray(nums)

Traversing

For traversing or in simple words - visiting all nodes in a linked list we can do something like this:

def traverseList(ll):
    curr = ll.head

    while curr:
        print(curr.data, end=" -> ")
        curr = curr.next

# traverse a linked-list O(n)
traverseList(ll)