Example of Linked List in Data Structure

Hello everyone, Today we are learning about Linked List. 

Linked List is an very useful algorithm that is used at the place of array when there is large amount of data to arrange or operate a large amount of data.

A linked list is a linear data structure where each element is a separate object.

Linked list elements are not stored at contiguous location; the elements are linked using pointers.

Each node of a list is made up of two items - the data and a reference to the next node. The last node has a reference to null. The entry point into a linked list is called the head of the list. It should be noted that head is not a separate node, but the reference to the first node. If the list is empty then the head is a null reference.

We can insert elements from beginning and end in a Linked List also same for deletions purposes.

Below there is an example of linked list with integer data:-

class Node:
    def __init__(self, value):
        self.val = value  # Assign value

        self.next = None  # Initialize next as null

class LinkedList:
    def __init__(self): # initializes linked list
        self.head = None

Above was the example to just give you an understanding about linked list.

Now lets see an example for all the operations:-

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

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

    def print(self):
        if self.head is None:
            print("Linked list is empty")
            return

        itr = self.head
        llstr = ''
        while itr:
              llstr += str(itr.data)+' --> ' if itr.next else str(itr.data)
 
            itr = itr.next
        print(llstr)

    def get_length(self):
        count = 0
        itr = self.head

        while itr:
            count += 1
            itr = itr.next
        return count

    def insert_at_begining(self, data):
        node = Node(data, self.head)
        self.head = node

    def insert_at_end(self, data):
        if self.head is None:
            self.head = Node(data, None)
            return

        itr = self.head
        while itr.next:
            itr = itr.next
        itr.next = Node(data, None)

    def insert_at(self, index, data):
          if index < 0 or index > self.get_length():
              raise Exception("Invalid Index")

        if index == 0:
            self.insert_at_begining(data)
            return
        count = 0
        itr = self.head
        while itr:
            if count == index - 1:

                  node = Node(data,itr.next)
                itr.next = node
                break
            itr = itr.next
            count += 1

    def remove_at(self, index):
          if index < 0 or index >= self.get_length():
              raise Exception("Invalid Index")

        if index == 0:
            self.head = self.head.next
            return
        count = 0
        itr = self.head
        while itr:
            if count == index - 1:
                  itr.next = itr.next.next
  
                break
            itr = itr.next
            count += 1

    def insert_values(self, data_list):
        self.head = None

        for data in data_list:
            self.insert_at_end(data)

if __name__ == '__main__':

    ll = LinkedList()

    ll.insert_values(["banana", "mango", "grapes", "orange"])
    ll.insert_at(1, "blueberry")
    ll.remove_at(2)
    ll.print()

    ll.insert_values([45, 7, 12, 567, 99])
    ll.insert_at_end(67)
    ll.print()

Output:-

banana --> blueberry --> grapes --> orange
45 --> 7 --> 12 --> 567 --> 99 --> 67