It’s a series of revising DS algo. Check this link for more details .
Intuition
A linked List is a data structure used for storing collections of data. A linked list has the following properties.
- Successive elements a re connected by pointers
- The last element points to NULL
- Can grow or shrink in size during execution of a program
- Can be made just as long as required (until systems memory exhausts)
- Docs not waste memory space (but takes some extra memory for pointers
A linked list is a dynamic data structure. The number of nodes in a list is not fixed and ca n grow and shrink on demand. Any application which has to deal with an unknown number of objects will need to use a linked list. lt is a very common data structure that is used to create other data structures like trees, graphs, hashing. etc.
Linked list could be singly , doubly or circular . Depending on your need you pick the one . You can perform insertion , deletion and many other operations on a linked list . You can implement linked list just by reviewing some articles and codes on that .
Basic Operations on Linked List
These are few operations on linked list and a short explanation to them . Operations like deleting entire list or printing the list in reverse order is all possible , just practice and think of these as intuitively .
1. Create a Class For Node . Initialize the Properties which are needed. (value and next):class Node:
def __init__(self,value,next = None):
self.value = value
self.next= next2. Create a Class For your linked list which will have an initialized First Node as None and other needed methods.class LinkedList:
def __init__(self):
self.head = None3. Now create those method which you have the need (inserting , deleting , displaying) in side the linked list class .Inserting at starting: Create a New Node. Then check if there is already a node in your list then link your new node to first node and then assign first node into new node . And if there is no nodes then assign first node as new node . def insertAtbegning(self,value):
newNode = Node(value)
if self.head != None:
newNode.next= self.head
self.head = newNode
else:
self.head = newNodeInserting at end : Create a new node and if there is already nodes in linked list then travel through the nodes .
def insertAtEnd(self,value):
newNode = Node(value)
if self.head != None:
current = self.head
while current.next != None:
current = current.next
current.next = newNode
else:
self.head = newNode4. Create a method which can display all the nodes of your linked list . And check if list is empty then return it and if it present then travel the list and display them def display(self):
if self.head == None:
print("List is empty")
return
current = self.head
while current.next != None:
print(current.value)
current = current.next5. Create a method which can delete the element by its value , and check if the list is empty then return it and if its not empty then check for the first element that , is it the target ? if ys then return . And if first node is not the target then travel the list and find . def delete(self,value):
if self.head == None:
print("list is empty")
return
if self.head == value:
temp = self.head
self.head = temp.next
temp = None
return
current = self.head
while current.next != None:
if current.next.value == value:
temp = current.next
current.next = temp.next
temp = None
return
current = current.next
print("Element is not found")
Talking About Complexities
Now as we perform any operation they will took some time and space to run . Let’s take an example of inserting , depending on how you are inserting the node in list , complexity will change also . Don't try to remember complexities for any operation , just find every time on your own .
Sources
My LinkedIn — linkedin.com/in/my-pro-file
To become a part of this series checkout this link .
