Linked List with Python
In programming world there is a concept of arrays, they help out our most of problems without any hurdles.
But you have to accept that some problems are very big and not tolerable also. One of the biggest problem is memory management.
Let's understand this memory management concept first.
Whatever thing you store in your memory is store in binary forms and you don't know where these data are stored, then array concept came in to action and made life easier of programmers.
You may ask how?
Let me clarify you, In other programming languages arrays can store only one data type at one time let's leave them and focus on Python.
In Python List is use on behalf of arrays(you can say it Dynamic Arrays).
One can store n numbers of data inside these dynamic arrays but there is memory management problem.
Array works like:- If you create an array you have to give size of it so let's consider 5 is size. If you want to store more values you have to create another array right? This was Static array now to solve this issue Dynamic Array introduced, it was able to solve this problem i.e. you don't have to give size of an array and if you stored 10 values in it and further after some time you want to enter 2 more values so your array will copy the data and make an array of double size then previous (previous was of size 10, now it will create size of 20 array) and paste previous values and next 2 values. But as you can see 8 boxes in arrays are empty means our memory is wasting and previous array is not deleted it is also stored in memory.
After this big issue solution came with Linked List. Linked List does not store values in arrays it take values with next address of data and keep the address to find them.
Head position of Linked List is always pointing to None you cannot fill any values there.
Linked List connected with nodes means each value is joined with next one's address.
Linked List is having one more type i.e. Double Linked List some people says Doubly Linked List whatever you want it is your choice.
Double Linked List is same as linked list but one difference is that it store data, previous and next data's address to keep in touch with them(to access them).
Let's understand Linked List with an example:-
class Node:
def __init__(self, data=None, next=None):
self.data = data
self.next = next
class LinkedList:
def __init__(self):
self.head = None
def insert_at_beginning(self, data):
node = Node(data, self.head)
self.head = node
def print(self):
if self.head is None:
print("Linked List is empty")
return
itr = self.head
linkstr = ""
while itr:
linkstr += str(itr.data) + "==>"
itr = itr.next
print(linkstr)
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 lengh_of_linkedlist(self):
count = 0
itr = self.head
while itr:
count += 1
itr = itr.next
return count
if __name__ == "__main__":
Llist = LinkedList()
Llist.insert_at_beginning(8)
Llist.insert_at_beginning(18)
Llist.insert_at_beginning(12)
Llist.insert_at_end(1)
Llist.insert_at_end(111)
Llist.insert_at_end(110)
Llist.print()
print("Length of this Linked List is:",Llist.lengh_of_linkedlist())
In above program as you can see there are 2 classes, first one is Node and another is LinkedList. In node class data and next variable is created to create data for linked list. In class LinkedList firstly head is initialized with None because as above you read that head should always be pointing to None. After that insert_at_beginning method is created to store values in beginning of Linked List. Then print method is created to print the linked list also you can see insert_at_end method is there to store values from last side of Linked List. After that lengh_of_linkedlist method is created to check the length of the Linked List. At last main functon is there in which object of LinkedList is created and all methods are called with the help of that object.
Output is:-
12==>18==>8==>1==>111==>110==>
Length of this Linked List is: 6