Linked List and Array are probably the most basic data structures, but their use can often be confusing. The use of the appropriate data structure can often result in an easier and more efficient code. Linked List vs Array is also a popular interview question in data structures.
Linked List vs Array
This article will provide an in-depth comparison of these two data structures.
We will compare them based on the following properties:
- Definitions and Structures
- Operations and Time Complexity Analysis
- Memory Analysis
- Codes (C and Python)
1. Definitions and Structures
Linked List is a data structure that stores linearly connected, non-contiguous data through references. This means that each node of the linked list would contain a reference to its next and/or previous node. This helps to make a chain of nodes that are linearly connected, but in memory, they may not be in a contiguous segment.
An array is a data structure that has a fixed size and contains a collection of data of a similar type that can be referenced through indexing. This means that before using an array we have to define its size and type and after storing the data we can refer to it using indexing.
In the memory, arrays are present in a contiguous block of data as well.
2D Arrays
2. Operations and Time Complexity Analysis
We will compare the data structures based on the following operations:
- Insertion and Deletion
- Accessing Elements
Insertion and Deletion
Insertion and Deletion in Linked List can be done at the beginning, in the middle or at the end.
- If insertion or deletion is done at the beginning, then we just need to reassign the references at the head thus, this is an O(1) operation.
- If insertion or deletion is done in the middle or at the end, then we first need to reach the required position in O(N) time and then reassign the references in O(1) time. This takes O(N + 1) = O(N) time.
Linked List Insertion
For an array, wherever the insertion or deletion is done, we always need to shift rest of the array to balance the indexing, thus these operations take O(1) time for doing the operation and O(N) time for balancing the indexing. Thus, it takes O(N + 1) = O(N) time always.
Array Insertion
Accessing Elements
In a Linked List, to access an element we have to reach its position through a traversal from the start that takes O(N) time.
In an array, we have indexes which we can directly refer to. This is useful because now, we don’t have to do a traversal and thus, accessing takes O(1) time.
3. Memory Analysis
Linked List is almost always a more memory efficient way to store data. This is because we assign the data in a Linked List dynamically, and its size can be shrunk and expanded according to use.
Arrays on the other hand, always have a fixed size. If an element is not assigned any value, then it still remains a part of the array and will still use up memory.
But this does not mean that arrays are always less efficient. Arrays only take up the memory that they are assigned whereas Linked List will take up memory for storing the data as well as storing the references. Also, for some operations like sorting, we need extra space to store and shift the elements, which is efficient in arrays.
Linked List Implementations
1. Python
|
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 |
class Node: def __init__(self, data): self.data = data self.next = None class LinkedList: """ Initialize the list by assigning head = NULL. """ def __init__(self): self.head = None ''' Returns the linear traversal of the Linked List in the form of a list. Initially, we can define a node that points to the head of the linked list and then we can keep sending it forward in the Linked List till we don't hit an end. ''' def traverse_list(self): # Node that points to the head, initially. cur = self.head ret = [] # Loop to send the cur node to the end. while cur: ret.append(cur.data) cur = cur.next # Returns the Linear Traversal in a list. return ret ''' To insert a node, we have 3 cases: 1) Empty List 2) Insertion at the beginning 3) Insertion in the middle/at the end For insertion at the end, we can loop till one element before the required position and then do the relinking of references. ''' def insert_node(self, pos, data): new_node = Node(data) cur_node = self.head # Case 1 : Empty List if cur_node is None: self.head = new_node # Case 2: Insertion at the beginning elif pos == 0: new_node.next = self.head self.head = new_node # Case 3: Insertion in the middle/at the end else: while pos - 1 > 0 and cur_node.next is not None: cur_node = cur_node.next pos -= 1 next_node = cur_node.next new_node.next = next_node cur_node.next = new_node return True ''' To delete a node, we have 5 cases: 1) Deletion from Empty List 2) Deletion at the beginning 5) Delete a node that does not exist 3) Deletion at the end 4) Deletion in the middle For deletion of a node, we first reach one node before the required position through a linear traversal and then relink the references accordingly. ''' def remove_node(self, pos): # Case 1 : Empty List if self.head is None: return False # Case 2 : Deletion at beginning elif pos == 0: self.head = self.head.next return True else: cur = self.head while pos - 1 > 0 and cur is not None: cur = cur.next pos -= 1 # Case 3 : Delete a node that does not exist if cur is None: return False # Case 4: Deletion at the end elif cur.next is None: cur = self.head while cur.next.next is not None: cur = cur.next cur.next = None return True # Case 5 : Deletion in the middle cur.next = cur.next.next return True a = LinkedList() a.insert_node(0, 3) a.insert_node(0, 2) a.insert_node(0, 1) print("Linked List :", a.traverse_list()) a.remove_node(2) print("Linked list :", a.traverse_list()) |
Output
2. C
|
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 |
#include<stdio.h> #include<stdlib.h> #include<stdbool.h> struct node{ int data; struct node *next; } *head = NULL; struct node *make_node(int data){ struct node *new = (struct node *)malloc(sizeof(struct node)); new->next = NULL; new->data = data; return new; } /* To insert a node, we have 3 cases: 1) Empty List 2) Insertion at the beginning 3) Insertion in the middle/at the end For insertion at the end, we can loop till one element before the required position and then do the relinking of references. */ bool insertNode(int pos, int data){ struct node *newNode = make_node(data), *curNode = head; //Case 1 : Empty List if(curNode == NULL){ head = newNode; } //Case 2: Insertion at the beginning else if(pos == 0){ newNode->next = head; head = newNode; } //Case 3: Insertion in the middle/at the end else{ while(pos - 1 > 0 && curNode->next != NULL){ curNode = curNode->next; pos--; } newNode->next = curNode->next; curNode->next = newNode; } return true; } /* Initially we can define a node that points to the head of the linked list and then we can keep sending it forward in the Linked List till we don't hit an end. */ void traverseList(){ struct node *cur = head; while(cur){ printf("%d ", cur->data); cur = cur->next; } printf("n"); } /* To delete a node, we have 5 cases: 1) Deletion from Empty List 2) Deletion at the beginning 5) Delete a node that does not exist 3) Deletion at the end 4) Deletion in the middle For deletion of a node, we first reach one node before the required position through a linear traversal and then relink the references accordingly. */ bool removeNode(int pos){ struct node *cur; //Case 1 : Empty List if(head == NULL) return false; //Case 2 : Deletion at beginning else if (pos == 0){ head = head->next; return true; } else{ cur = head; while (pos - 1 > 0 && cur != NULL){ cur = cur->next; pos--; } //Case 3 : Delete a node that does not exist if(cur == NULL) return false; //Case 4: Deletion at the end else if(cur->next == NULL){ cur = head; while(cur->next->next != NULL){ cur = cur->next; } cur->next = NULL; return true; } //Case 5 : Deletion in the middle cur->next = cur->next->next; return true; } } int main(){ insertNode(0, 3); insertNode(0, 2); insertNode(0, 1); traverseList(); removeNode(3); traverseList(); return 0; } |
Output
Arrays Implementations
1. Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
N = 10 singleDimensionalArray = [0 for i in range(N)] multiDimensionalArray = [[0 for x in range(N)] for y in range(N)] A = 4 pos = 5 singleDimensionalArray[pos] = A X, Y = 2, 3 multiDimensionalArray[X][Y] = A print(singleDimensionalArray) for i in multiDimensionalArray: print(i) |
Output:
2. C
|
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 |
#include<stdio.h> #include<stdlib.h> #include<stdbool.h> #define N 5 int main(){ int singleDimensionalArray[N] = {0}; int multiDimensionalArray[N][N] = {0}; int A = 4; int pos = 3, X = 2, Y = 3; singleDimensionalArray[pos] = A; multiDimensionalArray[X][Y] = A; int i, j; for(i = 0; i < N; i++){ printf("%d ", singleDimensionalArray[i]); } printf("nn"); for(i = 0; i < N; i++){ for(j = 0; j < N; j++){ printf("%d ", multiDimensionalArray[i][j]); } printf("n"); } return 0; } |
Output