-
Notifications
You must be signed in to change notification settings - Fork 191
/
Copy pathArray and Linkedlist Explanation(DSA)
164 lines (114 loc) · 47 KB
/
Array and Linkedlist Explanation(DSA)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
## 1. Linear Data Structure:
Linear data structure used to store homogeneous / Non homogeneous elements at contiguous locations.
**For example:** let us say, we want to store marks of all students in a class, we can use an list to store them. This helps in reducing the use of number of variables as we don’t need to create a separate variable for marks of every students. All marks can be accessed by simply traversing the list
## a) List Array
An list array is a collection of items stored at contiguous memory locations. The idea is to store multiple items of the same type together. This makes it easier to calculate the position of each element by simply adding an offset to a base value, i.e., the memory location of the first element of the list array (generally denoted by the name of the list array).
**Syntax:**
array(data type, value list)
1-import array as arr
a1=arr.array("i",[1,2,3,4,5])
a2=arr.array("f",[1.3,0.56,8.9])
a1.append(7)
a1.pop()
print(a1)
import array as arr
a1=arr.array("i",[1,2,3,4,5])
a2=arr.array("f",[1.3,0.56,8.9])
a1.insert(2,56)
print(a1)
i=signed
I=unsigned
**Operations on Array :**
i) **append()**:- This function is used to add the value mentioned in its arguments at the end of the array.
ii) **insert(i,x)** :- This function is used to add the value(x) at the ith position specified in its argument.
iii) **pop()**:- This function removes the element at the position mentioned in its argument and returns it.
iv) **remove()**:- This function is used to remove the first occurrence of the value mentioned in its arguments.
**Time Complexity**
Let size of list array be n.
**Accessing Time: O(1)** [This is possible because elements are stored at contiguous locations]
**Search Time: O(n)** for Sequential Search:
**O(log n)** for Binary Search [If Array is sorted]
**Insertion Time: O(n)** [The worst case occurs when insertion happens at the Beginning of an array and requires shifting all of the elements]
**Deletion Time: O(n)** [The worst case occurs when deletion happens at the Beginning of an array and requires shifting all of the elements]
## b) Linked list
A linked list is a linear data structure (like List arrays) where each element is a separate object. Each element (that is node) of a list is comprising of two items – the data and a reference to the next node.
**Advantages over arrays**
Ease of insertion/deletion
**Drawbacks:**
1) Random access is not allowed.
2) Extra memory space for a pointer is required with each element of the list.
3) Not cache friendly.
**Representation:**
**Operations on linkedlist :**
1-class Node:
def __init__(self,data):
self.data=data
self.next=None
class Linkedlist:
def __init__(self):
self.head=None
def view(self):
temp=self.head
while(temp!=None):
print(temp.data,end=" ")
temp=temp.next
def delfirst(self):
temp=self.head
self.head=temp.next
temp.next=None #temp is node1
node1=Node(8)
node2=Node(4)
node3=Node(5)
node4=Node(6)
l1=Linkedlist()
l1.head=node1
node1.next=node2
node2.next=node3
node3.next=node4
l1.view()
print()
l1.delfirst()
l1.view()
2-class Node:
def __init__(self,data):
self.data=data
self.next=None
class Linkedlist:
def __init__(self):
self.head=None
def view(self):
temp=self.head
while(temp!=None):
print(temp.data,end=" ")
temp=temp.next
def delfirst(self):
temp=self.head
self.head=temp.next
temp.next=None#temp node1 hai
def dellast(self):
temp=self.head
while temp.next.next!=None:
temp=temp.next
temp.next=None
node1=Node(8)
node2=Node(4)
node3=Node(5)
node4=Node(6)
l1=Linkedlist()
l1.head=node1
node1.next=node2
node2.next=node3
node3.next=node4
l1.view()
print()
l1.dellast()
l1.view()
i) **Linked List Traversal**
ii) **Delete first node**
iii) **delete last node**
iv) **delete any node**
v) **insert node at last**
vi) **insert node at first**
vii) **insert node before any node**