Singly Linked List
The following diagram shows a singly linked list of three elements:
Each element has two parts. The first part has the data. The second part has a pointer that points to the next element. The second and third elements are similar to the first. The last element has a null pointer. With the singly linked list, traversing can only go in one direction: the forward direction.
The elements of a linked list are not addressed by references (subscripts in square brackets), everything being equal. They are accessed by iterators (pointers). In the case of singly linked list, the iterator has to start from the beginning and move from element-by-element, in order to reach the intended element.
Doubly Linked List
The following diagram shows a doubly linked list of three elements:
Here, each element has three parts. The first part has a pointer that points to the previous element. The second part has the data. The third part has a pointer that points to the next element. The first part of the first element has a pointer that points to null. The third part of the last element has a pointer that points to null. With the doubly linked list, traversing can go in either direction: the forward direction or the reverse direction.
The elements of a linked list are not addressed by references (subscripts in square brackets). They are accessed by iterators (pointers). In the case of a doubly linked list, the iterator can move in either direction but has to start at either end. Movement cannot start officially from within the list.
The aim of this article is to determine what is known as the time complexity for the linked list.
Time Complexity in General
Time complexity is the relative runtime of some code. Time complexity can also be seen as the number of main operations of the code.
Constant Time
One main operation such as insert or delete is said to have a time complexity of constant time because the action can be seen as occurring once. It is written as:
O(1)
where 1 means constant time or action occurring once. This uses the Big-O notation which begins with O in uppercase followed by parentheses. Inside the parentheses is the number of main operations for the task.
Linear Time
Reading an array from the beginning— one element after the other looking for a particular element— is referred to as a linear search.
The element looked for may be found somewhere at the middle and the search would stop. This is still a linear search. The time complexity for linear search is written as:
O(n)
where n is the maximum possible number of operations.
Linked List Main Operations
Searching
For singly linked list, in order to move from one element to the next, the code has to use the current element’s pointer, that points to the next element. This is not the case with arrays. For doubly linked list, in order to move from one element to the next, the code has to use the current element’s pointer that points to the next element. This is not the case with arrays. For doubly linked list, in order to move from one element to the previous, the code has to use the current element’s pointer that points to the previous element. This is not the case with arrays.
Deletion
When a current element is deleted, the pointer of the previous element that was pointing to it, has to be made to point to the next element. Then, the pointer of the next element the was pointing to it has to be made to point to the previous element.
Insertion
When the current element is inserted, the pointer of the previous element that was pointing to the next element has to be made to point to the current element. The pointer of the next element that was pointing to the previous element has to be made to point to the current element.
The front pointer of the current element has to be made to point to the new next element. The back pointer of the current element has to be made to point to the new previous element.
Time Complexity for Linked List
When talking about time complexity for a linked list, it is the time complexity for search, insert, and delete that are talked about. It is not the time complexity for building the linked list that is talked about. Time complexity for building a linked list is a different issue.
Searching
For a singly linked list to be search for a particular element (data), the search code has to scan the list— element by element— from the beginning. For a doubly linked list to be search for a particular element, the search code has to scan the list— element by element— from the beginning. Or scan the list, element by element, from the end. The search time complexity for a linked list (singly or doubly) is:
O(n)
where n is the number of elements in the list. It does not matter if the element was found, somewhere within the list.
Insertion
Insertion is considered as one main operation. In order to insert an element in a linked list, searching has to take place, to arrive at the position, for insertion. The time complexity for searching is O(n). The time complexity for the action of inserting is O(1). So, the time complexity for insertion in a linked list is O(n + 1). For simplicity, the time complexity for insertion of an element, into a linked list, is written as:
O(n)
Deletion
Deletion is considered as one main operation. In order to delete an element in a linked list, searching has to take place, to arrive at the position for deletion. The time complexity for searching is O(n). The time complexity for the action of deleting, is O(1). So, the time complexity for deletion in a linked list is O(n + 1). For simplicity, the time complexity for deletion of an element, off a linked list, is written as:
O(n)
Building a Linked List in C
To build a doubly linked list in C, use the struct object. The first data member should have a pointer that points to the previous struct. The third data member should have a pointer that points to the next struct. The middle data member should have the data. The first data member of the first struct should point to null. The third data member of the last struct should also point to null.
In the case of singly linked list, omit the first data member.
Conclusion
The time complexity for searching a linked list is:
O(n)
For simplicity, the time complexity for inserting an element into a linked list is:
O(n)
and not O(1).
For simplicity, the time complexity for deletion of an element, off a linked list, is:
O(n)
and not O(1).
