Data Structure (Linked List Basics)

Pre requisite

• Basics of any Programming Language
• Basics of OOP (Object Oriented Programming)

Linked list is another type of data structure to store or arrange data. List may refer as an array, however linked list does not work like an array. Linked lists are actually created by objects where we can store each element on a single object.

Here we consider a single fruit basket as a single object and a single fruit as our data. It may seem a bit confusing now, but it will get much clearer when we get into it more. Pseudo code is given for a clear understanding.

object FruitBasket {
    variable initialising (fruit) {
        data = fruit
    }
}

fruit Basket One = FruitBasket(apple)
fruit Basket Two = FruitBasket(orange)
fruit Basket Three = FruitBasket(banana)

In this way we can store our data by passing into the object. Okay now you can say that we can do that with array as well. We can simply initialise an array with size one and pass our data. Yes, it is pretty much the same but there's more.

Suppose, we have hundreds of different kinds of fruits. Then we have to initialise array or make object hundred times. It is simple as we can always use loop. But how do we get access to all of them. Would you make hundred different variable for hundred different data? Here's where the 'Linked' word makes sense from the name Linked List.

How about instead of remembering hundreds of object locations, we remember only one object location and link the other objects to it. We just need to modify our code a little.

object FruitBasket {
    variable initialising (fruit) {
        data = fruit
        next node = null
    }
}

fruit Basket One = FruitBasket(apple)
fruit Basket Two = FruitBasket(orange)
fruit Basket Three = FruitBasket(banana)

We just added a new instance variable called next node and set it to null. Now the objects or in programmer convention 'Nodes' will look like this.

Now, we just need to pass in the next node location in this new variable to link with one another.

First, I pass in the location of node two in node one.

Then I pass in the location of node three in node two.

As a result, if we have access to node one then we can have access to node two. Then having access to node two, we can have access to node three. So, we only need the starting node (node one) or in programmer convention we call it the 'Head' to get access to the rest of the nodes. Pseudo code is given for better understanding.

object Node {
    variable initialising (fruit) {
        data = fruit
        next node = null
    }
}

Node One = Node(apple) #this object is our head
Node Two = Node(orange)
Node Three = Node(banana)
Node One.next node = Node Two
Node Two.next node = Node Three

We can even use only the Head to set these values.

Node one = Node(apple)
Node one.next node = Node(orange)
node one.next node.next node = Node(banana)

This way we have access to all the data using only one node location. In the end the last node will have null storing to it's 'next node' variable.

Now, it may seem a little frustrating to call the 'next node' instance variable this many times. What if there are hundreds of data.

So, as a challenge I want you to stop scrolling and find out a solution to store the data and next node location using a loop. You can consider there's a given array of many data and you have to create a linked list with the data. Solution is given below.

array = [apple, orange, banana]

Head = Node(array[first data])
current node = Head //so that we don't lose Head

for rest of the data in the array {
    temporary node = Node(data)
    current node.next node = temporary node
    current node = current node.next node
}

Now we have a linked list with a head.

How do we get access to all the data? we just simply run a while loop from head to the end of our linked list which is null and get data. Pseudo code is given below.

given head

current node = head
while current node is not null {
    get current node.data
    current node = current node.next node
}

Congratulations, you have completed the basic of a Linked List. Also, it is called Singly Linked list. I will post about different types of linked list later on.