SinglyLinkedListNode -LinkedList
Screen recording:https://www.youtube.com/watch?v=OxY7pf86J9Y
Before going to solve the problem just brief the theory
Comparing array versus list vs. LinkedList:
| List | array | LinkedList | |
| Insert at head (first) | O(n) | Inserting or deleting an element at an arbitrary position (assuming you know the position): O(n) | O(1) |
| Insert last at last element(Tail) | Appending a piece to the end: Amortized O(1) | Appending an element to the end: O(1) (assuming the array has available space) | Inserting or deleting an element at an arbitrary position (assuming you know the position): O(n) – if no tail is tracked O(1)-If the tail is tracked |
| Search | Accessing an element by index: O(1) Searching for an element: O(n) – linear search, unless the list is sorted and you use a binary search algorithm, which would be O(log n). | Accessing an element by index: O(1) | Accessing an element by index: O(n) – you have to traverse the list from the beginning to the desired position. Searching for an element: O(n) – linear search, unless the linked list is sorted and you use a binary search tree, which can reduce the complexity to O(log n). |
| Delete arbitrary position | Inserting or deleting an element at an arbitrary position (assuming you know the position): O(n) – because elements may need to be shifted. | O(n), an arbitrary element | Deleting an element at an arbitrary position O(n) |
| Deleting head | O(n) | O(n) | Inserting or deleting an element at the beginning (head): O(1) – These operations involve updating pointers at the head, so they are constant time |
| Deleting tail | O(1) | O(1) | Inserting or deleting an element at the end (tail): O(1) – If you maintain a reference to the tail node, these operations are constant time. |
Note:
If we need to perform frequent insertions at the head of a collection with better performance, consider using a data structure like a deque (double-ended queue) from the collections module. Deques are well-optimized for fast insertions and removals at both ends and can be more efficient for this purpose.
List:
Insert at head:
list.insert(0, value)
insert at tail:
list.append(value)
Search by in:my_list = [10, 20, 3, 4, 5]
element_to_search = 3
if element_to_search in my_list:
print (f"{elemnt_to_search} is avaible")
else:
print(f"{element_to_search} is not available")
Search by index():try:
found_index = list.index(elemnt_to_search):
print(f"{element_to_search} is available at index {found_index}")
Except ValueError:
print("Not avaible')
Delete:
If we know the value: remove()
my_list.remove(100)
if we know the index of a value:pop(index_of_the_value)
my_list(index_of_value)
Last element deletion :my_list.pop()
Array:
# Create an array of integers my_array = array(‘i’, [100, 200, 3, 4, 5])
Insert:
typical array
new_elemnt =10
index_to_insert = 0
my_array.insert(index_to_insert,new_element)
Using Numpy array
import numpy as np
index_to_new_element = 5
new_element_to_insert =10
inital_array = np.array([34,6,7,8,9,99])
new_array = np.insert(inital_array, index_to_new_element , new_element_to_insert, )
LinkedList:
class LinkedList:
def __init__(self):
self.head = Node('NULL')
def display_elements(self):
if self.head is None:
print("List is empty")
return
current = self.head
list_elements = ""
while current:
list_elements += str(current.data)
if current.next:
list_elements += "->"
current = current.next
print(list_elements)
def insert_at_head(self, data):
new_node = Node(data)
current_head = self.head
self.head = new_node
new_node.next = current_head
return True
def insert_at_tail(self, data):
new_node = Node(data)
if self.head is None:
self.head = new_node
return
current = self.head
while current.next:
current = current.next
current.next = new_node
link_list = LinkedList()
link_list.insert_at_head(10)
link_list.insert_at_head(20)
link_list.display_elements()
Sharing Knowledge and programming 