[DS] 01 Array List vs Linked List
Published:
In this post, we compare array list and linked list.
Python List
In python, a list is implemented underneath with an array. This leads to the following inefficiencies:
- When inserting an element, all elements from the insertion point to the end must be shifted one position to the right.
- When deleting an element, all elements from the deletion point to the end must be shifted one position to the left.
- Arrays allocate space in advance, leading to space wastage.
Python’s built-in list automatically handles situations like this (e.g. when attempting to insert an element when the space is full, it allocates a new array, copies the contents of the existing array, and remaps the list to the new array). However, longer lists can lead to wastage of space and performance degradation.
Linked List
Linked lists follow a dynamic allocation approach where space is allocated every time an element is added, avoiding wastage of space.
Below is a Python code implementing only the insertion process of a linked list, distinguishing between inserting at index 0 and other indices:
class ListNode:
def __init__(self, newItem, nextNode:'ListNode'):
self.item = newItem
self.next = nextNode
from ListNode import ListNode
# not using dummy Node
class LinkedListBasic:
def __init__(self):
self.__head = None
self.__numItems = 0
def insert(self, i, newItem):
if i>0 :
prev = self.get(i-1)
newNode = ListNode(newItem, prev.next)
prev.next = newNode
self.__numItems +=1
elif i==0 :
newNode = ListNode(newItem, self.__head)
self.__head = newNode
self.__numItems +=1
However, by using a dummy node so that the head points to it, there will always be a previous node before the node to be inserted, eliminating the need to consider cases where the node to be inserted is at the beginning.
from ListNode import ListNode
# using dummy Node
class LinkedListBasic:
def __init__(self):
self.__head = ListNode('dummy', None)
self.__numItems = 0
def insert(self, i:int, newItem):
if i >= 0 and i <= self.__numItems:
prev = self.__getNode(i-1)
newNode = ListNode(newItem, prev.next)
prev.next = newNode
self.__numItems +=1
else:
print("index out of range")
def append(self, newItem):
prev = self.__getNode(self.__numItems-1)
newNode = ListNode(newItem, prev.next)
prev.next = newNode
self.__numItems += 1
def pop(self, i:int):
if i >= 0 and i <= self.__numItems-1:
prev = self.__getNode(i-1)
curr = prev.next
prev.next = curr.next
retItem = curr.item
self.__numItems -= 1
return retItem
else :
return None
def remove(self, x):
(prev, curr) = self.__findNode(x)
if curr != None:
prev.next = curr.next
self.__numItems -= 1
def __getNode(self, i:int):
curr = self.__head
for index in range(i+1):
curr = curr.next
return curr
def __findNode(self, x) -> (ListNode, ListNode):
prev = self.__head
curr = prev.next
while curr != None:
if curr.item == x:
return (prev, curr)
else:
prev, curr = curr, curr.next
return (None, None)
def get(self, i:int):
if self.isEmpty():
return None
elif i >= 0 and i <= self.__numItems - 1:
return self.__getNode(i).item
else:
return None
def index(self, x) -> int:
curr = self.__head.next
for index in range(self.__numItems):
if curr.item == x:
return index
else:
curr = curr.next
return -12345
def count(self, x) -> int:
cnt = 0
curr = self.__head.next
while curr != None:
if curr.item == x:
cnt += 1
curr = curr.next
return cnt
def extend(self, a):
for index in range(a.size()):
self.append(a.get(index))
def copy(self):
a = LinkedListBasic()
for index in range(self.__numItems):
a.append(self.get(index))
return a
def reverse(self):
a = LinkedListBasic()
for index in range(self.__numItems):
a.insert(0, self.get(index))
self.clear()
for index in range(a.size()):
self.append(a.get(index))
def sort(self) -> None:
a = []
for index in range(self.__numItems):
a.append(self.get(index))
a.sort
self.clear()
for index in range(len(a)):
self.append(a[index])
def isEmpty(self) -> bool:
return self.__numItems == 0
def size(self) -> int:
return self.__numItems
def clear(self):
self.__head = ListNode("dummy", None)
self.__numItems = 0
def printList(self):
curr = self.__head.next
while curr != None:
print(curr.item, end = ' ')
curr = curr.next
print()
The above implementation includes several inefficiencies:
- In the
append()method, a for loop is used to access the last element of the list. Similarly,extend(),copy(), andreverse()also involve looping. If these operations are used repeatedly, it incurs significant time overhead. - The
reverse()method also adds the burden of creating a new list of the same size as the list being copied.
Array List vs Linked List
Let’s compare Array List and Linked List from the perspective of time complexity (worst case):
Accessing the i-th element:
- Array List: O(1)
- Linked List: O(n)
Searching for a specific element:
- Sorted Array List: O(nlogn) (using binary search algorithm)
- Unsorted Array List: O(n)
- Sorted Linked List: O(n)
- Unsorted Linked List: O(n)
Adding/removing an element:
- Array List: O(n) (when inserting/deleting data at the beginning of the array, shifting n existing data)
- Linked List: O(n) (the main process of inserting/deleting by modifying the links of surrounding nodes is O(1), but finding the node to insert/delete is O(n))
From a memory perspective, as mentioned earlier, Linked List offers superior memory efficiency.
Leave a Comment