1+ """
2+ Linked Lists:
3+ Single Linked Lists:
4+ |data|LinkToNextData|--->|data|LinkToNextData|--->|data|null|
5+ (disadvantage: can't go back to previous data after one data point)
6+
7+ Double Linked List:
8+ |Null|data|LinkToNextData|<--->|LinkToPreviousData|data|LinkToNextData|<--->|LinkToPreviousData|data|null|
9+
10+ Advantage of Linked List over array:
11+ > No need to pre-allocate the space
12+ > Insertion is easier
13+
14+ BigO of Linked List:
15+ Indexing -----> O(n)
16+ Insert/Delete element at Start -----> O(1)
17+ Insert/Delete element at End -----> O(n)
18+ Insert element at Middle -----> O(n)
19+ Linked List Traversal(Reverse) -----> O(n)
20+ Accessing Elements by Value -----> O(n)
21+ """
22+
23+ class Node :
24+ '''
25+ Working of Class Node:
26+ whenever this class is called, a data will be passed which will get saved in LinkedList as a node which has 2 parts: data & next
27+ '''
28+ def __init__ (self , data = None , next = None ): # initialised data to None
29+ self .data = data
30+ self .next = next
31+
32+ class LinkedList ():
33+ def __init__ (self ):
34+ self .head = Node () # Head is starting point of a Linked List and points to no other value
35+
36+ # def accept_data(self, data):
37+ def accept_data (self , * data ): # args to get data at single go
38+ new_node = Node (data ) # created a new node to add data
39+ cur = self .head # pointer set for the next data
40+ while cur .next != None :
41+ # let linked list have 5 elements; new node will be added as 6th node in linkedlistl;
42+ # so we will have to search for the last pointer (ptr of 5th ele)
43+ # so we will iterate until ptr of of curent ele becomes none; as it gets None we will come to know that this is the last node
44+ cur = cur .next
45+ cur .next = new_node # pointer set to the new node
46+
47+
48+ # method to print each element of Linked List
49+ def display (self ):
50+ disp = []
51+ cur = self .head
52+ disp .append (cur .data ) # to display head element
53+
54+ while cur .next != None : # will iterate until next val of current pointer gets None
55+ cur = cur .next # accessing next element of the node
56+ disp .append (cur .data ) # appended the data of current element to the list disp[]
57+ print (disp )
58+
59+ # Method to get length of elements in Linked List
60+ def getLength (self ):
61+ count = 0
62+ itr = self .head
63+ while itr :
64+ count += 1
65+ itr = itr .next
66+ return count
67+
68+ def removeAtIndex (self , index ):
69+ # check if index is valid
70+ if index < 0 or index >= self .getLength ():
71+ raise Exception ("Invalid Index" )
72+
73+ if index == 0 : # removing head
74+ self .head = self .head .next
75+ return
76+
77+ count = 0
78+ itr = self .head
79+ while itr :
80+ # removing element at given index
81+ if count == index - 1 : # we need to stop at the element prior to element we are removing
82+ # After element(e1) is removed, address of e2 is linked to e0
83+ itr .next = itr .next .next
84+ break
85+ itr = itr .next
86+ count += 1
87+
88+
89+ def insertAtIndex (self , index , data ):
90+ # check if index is valid
91+ if index < 0 or index >= self .getLength ():
92+ raise Exception ("Invalid Index" )
93+
94+ if index == 0 : # value is inserted at index[0]
95+ self .accept_data (data )
96+ return
97+
98+ count = 0
99+ itr = self .head
100+ while itr :
101+ if count == index - 1 :
102+ node = Node (data , itr .next )
103+ itr .next = node
104+ itr = itr .next
105+ count += 1
106+
107+
108+
109+ l = LinkedList () # created an object 'l' to call class LinkedList
110+
111+ # adding elements to linked list one-by-one
112+
113+ l .head = Node (1 ) # Head of the Linked List
114+ element2 = Node (2 )
115+ element3 = Node (3 )
116+ element4 = Node (4 )
117+
118+ # Linking Nodes of the Linked List to each other
119+ # if not linked, only value at head will be printed
120+ l .head .next = element2 # head is pointing to element2
121+ element2 .next = element3 # element2 is pointing to element3
122+ element3 .next = element4 # element3 is pointing to element4
123+
124+ # display Linked List
125+ l .display ()
126+ print ("Length: " , l .getLength ())
127+ l .removeAtIndex (2 )
128+ l .display ()
129+ l .insertAtIndex (2 , 3 ) # (index, value)
130+ l .display ()
131+
132+ # adding elements of LinkedList at once
133+ # l = LinkedList()
134+ # l.accept_data(1,2,3,4,5)
135+
136+
137+ # if function accept_data is used without (*data) as parameter
138+ # adding values one-by-one
139+ # l.accept_data(1)
140+ # l.accept_data(2)
141+ # l.accept_data(3)
142+ # l.accept_data(4)
143+ # l.accept_data(5)
144+ # l.display()
0 commit comments