-
Notifications
You must be signed in to change notification settings - Fork 0
/
linkedlist.html
150 lines (131 loc) · 6.17 KB
/
linkedlist.html
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
<!DOCTYPE html>
<html>
<head>
<title>Linked Lists and Arrays</title>
<style>
body {
background: linear-gradient(90deg,rgba(63,94,251,1) 0%, rgba(135,252,70,1) 100%);
font-family: Arial, sans-serif;
color: white;
}
.container {
max-width: 800px;
margin: 0 auto;
padding: 40px;
background-color: rgba(0, 0, 0, 0.7);
border-radius: 5px;
box-shadow: 0 2px 5px rgba(0, 0, 0, 0.3);
}
h1 {
text-align: center;
}
p, ul, ol, table {
margin: 10px 0;
}
ul, ol {
padding-left: 20px;
}
table {
width: 100%;
border-collapse: collapse;
}
th, td {
padding: 8px;
border: 1px solid #cccccc;
}
th {
background-color: #f2f2f2;
font-weight: bold;
text-align: left;
}
h2, h3, h4, h5, h6 {
margin-top: 20px;
}
h2 {
font-size: 24px;
}
h3 {
font-size: 20px;
}
h4 {
font-size: 18px;
}
h5 {
font-size: 16px;
}
h6 {
font-size: 14px;
}
</style>
</head>
<div class="container">
<body>
<h1>Linked Lists and Arrays</h1>
<p>Linked lists and arrays are similar since they both store collections of data. Arrays are the most common data structure used to store collections of elements. Arrays are convenient to declare and provide easy syntax to access any element by its index number. Once the array is set up, access to any element is convenient and fast. However, arrays have some disadvantages:</p>
<ul>
<li>The size of the array is fixed, often specified at compile time.</li>
<li>Inserting new elements at the front is potentially expensive because existing elements need to be shifted over to make room.</li>
<li>Deleting an element from an array is not possible.</li>
</ul>
<p>Linked lists have their own strengths and weaknesses. They allocate memory for each element separately and only when necessary. Here is a quick review of the terminology and rules of pointers.</p>
<h2>Linked List Concepts</h2>
<p>A linked list is a non-sequential collection of data items. It is a dynamic data structure where each data item has an associated pointer that points to the memory location of the next data item. Linked lists have several advantages:</p>
<ul>
<li>Linked lists are dynamic data structures that can grow or shrink during program execution.</li>
<li>Linked lists have efficient memory utilization as memory is allocated whenever required and deallocated when no longer needed.</li>
<li>Insertion and deletion are easier and efficient in linked lists.</li>
<li>Linked lists can be used to implement complex applications such as stacks, queues, trees, and graphs.</li>
</ul>
<p>However, linked lists also have some disadvantages:</p>
<ul>
<li>Linked lists consume more space as each node requires an additional pointer to store the address of the next node.</li>
<li>Searching a particular element in a linked list is difficult and time-consuming.</li>
</ul>
<h3>Types of Linked Lists</h3>
<p>There are several types of linked lists:</p>
<ol>
<li>Single Linked List</li>
<li>Double Linked List</li>
<li>Circular Linked List</li>
<li>Circular Double Linked List</li>
</ol>
<h4>Comparison between Array and Linked List</h4>
<table>
<tr>
<th>Feature</th>
<th>Array</th>
<th>Linked List</th>
</tr>
<tr>
<td>Size</td>
<td>Fixed</td>
<td>Not fixed</td>
</tr>
<tr>
<td>Memory Allocation</td>
<td>Stack</td>
<td>Heap</td>
</tr>
<tr>
<td>Insertion at Front</td>
<td>Potentially expensive</td>
<td>Easy</td>
</tr>
<tr>
<td>Deletion</td>
<td>Not possible</td>
<td>Possible</td>
</tr>
</table>
<h5>Trade-offs between Linked Lists and Arrays</h5>
<p>Linked lists.
<li>Accessing elements: In an array, accessing elements by their index is efficient and has a constant time complexity of O(1). In a linked list, accessing elements by their position requires traversing the list from the beginning, resulting in a time complexity of O(n), where n is the number of elements in the list.</li>
<li>Insertion and deletion: Linked lists have an advantage when it comes to inserting and deleting elements. Inserting or deleting an element at the front of a linked list can be done in constant time, O(1), since it only involves updating the pointers. In contrast, inserting or deleting an element in an array requires shifting elements, resulting in a time complexity of O(n), where n is the number of elements in the array.</li>
<li>Memory allocation: Arrays are allocated in a contiguous block of memory, while linked lists use dynamic memory allocation, allocating memory for each node individually. This means that arrays require a fixed amount of memory, specified at compile time, while linked lists can grow or shrink during program execution.</li>
<li>Memory utilization: Linked lists have efficient memory utilization since memory is allocated only when necessary. In contrast, arrays require a fixed amount of memory, even if some elements are unused.</li>
<li>Search operation: Searching for a specific element in an array can be done efficiently using binary search if the array is sorted. Binary search has a time complexity of O(log n), where n is the number of elements in the array. In a linked list, searching for an element requires traversing the list sequentially, resulting in a time complexity of O(n).</li>
</ul>
<h6>Conclusion</h6>
<p>In conclusion, linked lists and arrays have different characteristics and trade-offs. Arrays provide efficient random access and are suitable for scenarios where the size of the collection is known in advance and needs to be accessed frequently. On the other hand, linked lists are more flexible in terms of size and efficient for inserting and deleting elements. The choice between the two depends on the specific requirements of your application.</p>
</div>
</html>