## Problem Statement

Given a singly linked list, use the merge sort algorithm to sort the list in the ascending order of their node’s values.

## Example

### Input

`4 --> 3 --> 2 --> 5 --> 1 --> null`

### Output

`1 --> 2 --> 3 --> 4 --> 5 --> null`

## Example Explanation

The nodes in the input are not arranged in any particular order, while they are arranged in ascending order of their value in the output.

## Constraints

- $0 < n < 10^5,$ where $n$ is the number of nodes.
- $-10^9 < \text{node.val} < 10^9$

## Algorithm 1

Merge sort for linked lists is preferred to sort linked lists because accessing a random node in a linked list is a costly operation which makes other algorithms like quicksort, heapsort, etc inefficient.

The algorithm of merge sort for linked lists is quite similar to sorting an array using merge sort. We will be having a recursive function `mergeSort`

which divides the list into two halves and recurse back for the left and the right half. After that, we will have another function `mergeSorted`

which will be used to merge the sorted parts.

The steps required in the algorithm are as follows –`mergeSort(head)`

–

- Let the function be
`mergeSort`

that accepts a single argument`head`

which denotes the pointer to the head of the linked list. - In the function, firstly we will check if the
`head`

itself is null or if the list with its head node as`head`

consists of only one node. If any of the above conditions is found to be true, we will simply return`head`

. - Now we will find the middle node of the liked list whose head node is
`head`

, let it be`mid`

. - Now we will divide the list into two halves, therefore we will remove the
`next`

link of the`mid`

node $i.e.$`mid.next = null`

. - Recur for the left and right half of the partitioned list, let the node returned by them be
`left`

and`right`

respectively. - Call the
`mergeSorted`

function to merge the sorted left part and the sorted right part. Let after merging two individually sorted parts, the head node of the combined linked list is`answer`

. - Return the
`answer`

node which represents the head of the sorted linked list.

The steps required to merge the sorted parts are as follows –`mergeSorted(left, right)`

–

- Let the function
`mergeSorted`

accepts two arguments of node type`left`

and`right`

denoting the head of two independent sorted lists. - Now we will have some base conditions –
- If
`left`

is null then return`right`

. - Else if
`right`

is null then return`left`

.

- If
- Then we will declare a node type variable
`res`

to store the result. - Now we will check if
`left.val`

is smaller than or equal to`right.val`

, then we will assign`left`

to`res`

and recurse for the`left.next`

and assign the obtained result to`res.next`

. - Now we will check if
`left.val`

is greater than`right.val`

, then we will assign`right`

to`res`

and recurse for the`right.next`

and assign the obtained result to`res.next`

. - At last we will return the
`res`

as our answer.

### Java Implementation

```
// Java program to sort a linked list
// using the merge sort algorithm.
public class Main{
// Node class
static class Node{
int val;
// Pointer to its next node
Node next;
// Constructor
Node(int val){
this.val = val;
}
}
// Function to print the list
static void printList(Node head){
// Iterating while head is not null.
while (head != null){
System.out.print(head.val + " ");
head = head.next;
}
System.out.println();
}
// Function to find the middle
// node of the linked list.
static Node findMiddle(Node head){
// Base condition.
if (head == null)
return head;
// Slow and fast pointers to
// iterate over the list.
// Fast pointer will take 2 steps
// at a time while slow pointer will
// take 1 step at a time.
Node slow = head, fast = head;
// Iterating while we have reached
// last or second last node of the list.
while (fast.next != null && fast.next.next != null){
fast = fast.next.next;
slow = slow.next;
}
// Node pointed by the slow pointer is the middle
// node of the list.
return slow;
}
// Function to merge two already sorted lists.
static Node mergeSorted(Node left, Node right){
// Base cases to check if either of
// the list provided is empty.
if (left == null)
return right;
if (right == null)
return left;
// Declaring the variable 'res' to hold
// the result.
Node res = null;
// If left's val is smaller than or equal
// to right's val.
if (left.val <= right.val){
// Assigning left to res.
res = left;
// Recurring for left.next and
// assigning answer to res.next.
res.next = mergeSorted(left.next, right);
}
// Otherwise left's val is greater than
// right's val.
else {
// Assigning right to res.
res = right;
// Recurring for right.next and
// assigning answer to res.next.
res.next = mergeSorted(left, right.next);
}
// Returning the result.
return res;
}
// Function to sort the list.
static Node mergeSort(Node head){
// Base condition to check if the head
// itself is null or the list consists of
// only a single node.
if (head == null || head.next == null){
return head;
}
// Finding the middle node of the list.
Node mid = findMiddle(head);
// Finding the next node of the middle node.
Node nextToMid = mid.next;
// Breaking the list into two halves.
mid.next = null;
// Recurring for the left and the right
// halves obtained.
Node left = mergeSort(head);
Node right = mergeSort(nextToMid);
// Merging the already sorted left
// and right part of the linked list.
Node res = mergeSorted(left, right);
// Returning the result.
return res;
}
public static void main(String args[]){
// Constructing the following linked list.
// 4 --> 3 --> 2 --> 5 --> 1 --> null
Node head = new Node(4);
head.next = new Node(3);
head.next.next = new Node(2);
head.next.next.next = new Node(5);
head.next.next.next.next = new Node(1);
// Printing the list before sorting.
System.out.println("List before sorting - ");
printList(head);
// Calling the function to sort the list.
head = mergeSort(head);
// Printing the list after sorting.
System.out.println("List after sorting -");
printList(head);
}
}
```

**Output –**

```
List before sorting -
4 3 2 5 1
List after sorting -
1 2 3 4 5
```

### C++ Implementation

```
// C++ program to sort a linked list
// using the merge sort algorithm.
#include<bits/stdc++.h>
using namespace std;
// Node class
class Node{
public:
int val;
// Pointer to its next node
Node *next;
// Constructor
Node(int Val){
val = Val;
}
};
// Function to print the list
void printList(Node *head){
// Iterating while head is not nullptr.
while (head != nullptr){
cout << head->val << " ";
head = head->next;
}
cout << endl;
}
// Function to find the middle
// node of the linked list.
Node *findMiddle(Node *head){
// Base condition.
if (head == nullptr)
return head;
// Slow and fast pointers to
// iterate over the list.
// Fast pointer will take 2 steps
// at a time while slow pointer will
// take 1 step at a time.
Node *slow = head, *fast = head;
// Iterating while we have reached
// last or second last node of the list.
while (fast->next != nullptr && fast->next->next != nullptr){
fast = fast->next->next;
slow = slow->next;
}
// Node pointed by the slow pointer is the middle
// node of the list.
return slow;
}
// Function to merge two already sorted lists.
Node *mergeSorted(Node *left, Node *right){
// Base cases to check if either of
// the list provided is empty.
if (left == nullptr)
return right;
if (right == nullptr)
return left;
// Declaring the variable 'res' to hold
// the result.
Node *res = nullptr;
// If left's val is smaller than or equal
// to right's val.
if (left->val <= right->val){
// Assigning left to res->
res = left;
// Recurring for left->next and
// assigning answer to res->next->
res->next = mergeSorted(left->next, right);
}
// Otherwise left's val is greater than
// right's val.
else {
// Assigning right to res->
res = right;
// Recurring for right->next and
// assigning answer to res->next->
res->next = mergeSorted(left, right->next);
}
// Returning the result.
return res;
}
// Function to sort the list.
Node *mergeSort(Node *head){
// Base condition to check if the head
// itself is nullptr or the list consists of
// only a single node.
if (head == nullptr || head->next == nullptr){
return head;
}
// Finding the middle node of the list.
Node *mid = findMiddle(head);
// Finding the next node of the middle node.
Node *nextToMid = mid->next;
// Breaking the list into two halves.
mid->next = nullptr;
// Recurring for the left and the right
// halves obtained.
Node *left = mergeSort(head);
Node *right = mergeSort(nextToMid);
// Merging the already sorted left
// and right part of the linked list.
Node *res = mergeSorted(left, right);
// Returning the result.
return res;
}
int main(){
// Constructing the following linked list.
// 4 --> 3 --> 2 --> 5 --> 1 --> nullptr
Node *head = new Node(4);
head->next = new Node(3);
head->next->next = new Node(2);
head->next->next->next = new Node(5);
head->next->next->next->next = new Node(1);
// Printing the list before sorting.
cout << "List before sorting - " << endl;
printList(head);
// Calling the function to sort the list.
head = mergeSort(head);
// Printing the list after sorting.
cout << "List after sorting -" << endl;
printList(head);
return 0;
}
```

**Output –**

```
List before sorting -
4 3 2 5 1
List after sorting -
1 2 3 4 5
```

### Python Implementation

```
# Python program to sort a linked list
# using the merge sort algorithm.
class Node:
# Constructor
def __init__(self, val):
self.val = val
self.next = None
# Function to print the list
def printList(head):
# Iterating while head is not None.
while (head != None):
print(head.val, end = " ")
head = head.next
print()
# Function to find the middle
# node of the linked list.
def findMiddle(head):
# Base condition.
if (head == None):
return head
# Slow and fast pointers to
# iterate over the list.
# Fast pointer will take 2 steps
# at a time while slow pointer will
# take 1 step at a time.
slow, fast = head, head
# Iterating while we have reached
# last or second last node of the list.
while (fast.next != None and fast.next.next != None):
fast = fast.next.next
slow = slow.next
# Node pointed by the slow pointer is the middle
# node of the list.
return slow
# Function to merge two already sorted lists.
def mergeSorted(left, right):
# Base cases to check if either of
# the list provided is empty.
if (left == None):
return right
if (right == None):
return left
# Declaring the variable 'res' to hold
# the result.
res = None
# If left's val is smaller than or equal
# to right's val.
if (left.val <= right.val):
# Assigning left to res.
res = left
# Recurring for left.next and
# assigning answer to res.next.
res.next = mergeSorted(left.next, right)
# Otherwise left's val is greater than
# right's val.
else:
# Assigning right to res.
res = right
# Recurring for right.next and
# assigning answer to res.next.
res.next = mergeSorted(left, right.next)
# Returning the result.
return res
# Function to sort the list.
def mergeSort(head):
# Base condition to check if the head
# itself is None or the list consists of
# only a single node.
if (head == None or head.next == None):
return head
# Finding the middle node of the list.
mid = findMiddle(head)
# Finding the next node of the middle node.
nextToMid = mid.next
# Breaking the list into two halves.
mid.next = None
# Recurring for the left and the right
# halves obtained.
left = mergeSort(head)
right = mergeSort(nextToMid)
# Merging the already sorted left
# and right part of the linked list.
res = mergeSorted(left, right)
# Returning the result.
return res
# Constructing the following linked list.
# 4 --> 3 --> 2 --> 5 --> 1 --> None
head = Node(4)
head.next = Node(3)
head.next.next = Node(2)
head.next.next.next = Node(5)
head.next.next.next.next = Node(1)
# Printing the list before sorting.
print("List before sorting - ")
printList(head)
# Calling the function to sort the list.
head = mergeSort(head)
# Printing the list after sorting.
print("List after sorting -")
printList(head)
```

**Output –**

```
List before sorting -
4 3 2 5 1
List after sorting -
1 2 3 4 5
```

### Complexity Analysis

**Time Complexity –**At each iteration, we are dividing the list into two halves and in each step, we are merging the divided parts. Since the merging step requires $O(n)$ time and there are $O(\log_2{n}$] iterations, therefore, the overall time complexity is $O(n\log_2{n})$.**Space Complexity –**Since both of the used functions (`mergeSort`

and`mergeSorted`

) are recursive in nature they will require $O(\log_2{n})$ and $O(n)$ recursive stack space respectively. Hence, the overall space complexity is $O(n)$.

## Approach 2

In our last algorithm, we have seen how to use merge sort for linked lists. In this approach, we will be seeing the same concept again and will try to reduce the space complexity of the algorithm.

Last time we implemented `mergeSorted()`

function in a recursive manner which is why it required $O(n)$ recursive stack space. But this time we will try to optimize it such that `mergeSorted()`

function will require constant extra space.

The algorithm of the `mergeSort()`

function is the same as in the previous section, hence we are not including it again. However, the `mergeSorted()`

algorithm is now changed and is as follows –`mergeSorted(left, right)`

- Let the arguments accepted by the
`mergeSorted()`

function be nothing but the heads of already sorted linked lists. - As part of our base condition we will be checking if any of the lists is empty.
- Then we will declare a node type variable
`dummy`

with value 1 and another node type variable`node`

that will point to dummy. The`dummy`

will help to return the answer at the end of the function and the`node`

is required to traverse the list. - Now we will use a while loop to traverse until either of the
`left`

or`right`

pointer does not point to null and do the following –- If left’s val is smaller than or equal to right’s val then –
- Assign left to
`node.next`

. - Move left to its next pointer.

- Assign left to
- Otherwise, left’s val is greater than right’s val –
- Assign right to
`node.next`

. - Move right to its next pointer.

- Assign right to
- At last move node to its next pointer $i.e.$
`node = node.next`

.

- If left’s val is smaller than or equal to right’s val then –
- After exiting from loop we will be including the nodes left out in the lists. Therefore, we will iterate until the
`left`

pointer does not start pointing to null and do the following –- Assign left to
`node.next`

. - Move left to its next pointer.
- Move node to its next pointer $i.e.$
`node = node.next`

.

- Assign left to
- We will repeat the above process for the
`right`

list $i.e.$ iterate until the`right`

pointer does not start pointing to null and do the following –- Assign right to
`node.next`

. - Move right to its next pointer.
- Move node to its next pointer $i.e.$
`node = node.next`

- Assign right to
- Now the merging part is done, we just need to return the head of the merged list which is pointed by
`dummy.next`

. Therefore, we will simply return`dummy.next`

.

### Java Implementation

```
// Java program to sort a linked list
// using the merge sort algorithm.
public class Main{
// Node class
static class Node{
int val;
// Pointer to its next node
Node next;
// Constructor
Node(int val){
this.val = val;
}
}
// Function to print the list
static void printList(Node head){
// Iterating while head is not null.
while (head != null){
System.out.print(head.val + " ");
head = head.next;
}
System.out.println();
}
// Function to find the middle
// node of the linked list.
static Node findMiddle(Node head){
// Base condition.
if (head == null)
return head;
// Slow and fast pointers to
// iterate over the list.
// Fast pointer will take 2 steps
// at a time while slow pointer will
// take 1 step at a time.
Node slow = head, fast = head;
// Iterating while we have reached
// last or second last node of the list.
while (fast.next != null && fast.next.next != null){
fast = fast.next.next;
slow = slow.next;
}
// Node pointed by the slow pointer is the middle
// node of the list.
return slow;
}
// Function to merge two already sorted lists.
static Node mergeSorted(Node left, Node right){
// Base cases to check if either of
// the list provided is empty.
if (left == null)
return right;
if (right == null)
return left;
// Dummy node to hold the answer.
Node dummy = new Node(-1);
// Declaring another variable 'node'
// to iterate further
Node node = dummy;
// Iterating while both pointers
// are not null
while (left != null && right != null){
// If left's val is smaller than or
// equal to right's val.
if (left.val <= right.val){
// Assign left to node's next.
node.next = left;
// Move left to its next node.
left = left.next;
}
// Otherwise left's val is greater
// than right's val.
else{
// Assign right to node's next.
node.next = right;
// Move right to its next.
right = right.next;
}
// Moving node to its next node.
node = node.next;
}
// Iterating while left is not null.
while (left != null){
// Assign left to node's next.
node.next = left;
// Move left to its next node.
left = left.next;
// Moving node to its next node.
node = node.next;
}
// Iterating while right is not null.
while (right != null){
// Assign right to node's next.
node.next = right;
// Move right to its next.
right = right.next;
// Moving node to its next node.
node = node.next;
}
// Returning dummy's next as our answer.
return dummy.next;
}
// Function to sort the list.
static Node mergeSort(Node head){
// Base condition to check if the head
// itself is null or the list consists of
// only a single node.
if (head == null || head.next == null){
return head;
}
// Finding the middle node of the list.
Node mid = findMiddle(head);
// Finding the next node of the middle node.
Node nextToMid = mid.next;
// Breaking the list into two halves.
mid.next = null;
// Recurring for the left and the right
// halves obtained.
Node left = mergeSort(head);
Node right = mergeSort(nextToMid);
// Merging the already sorted left
// and right part of the linked list.
Node res = mergeSorted(left, right);
// Returning the result.
return res;
}
public static void main(String args[]){
// Constructing the following linked list.
// 4 --> 3 --> 2 --> 5 --> 1 --> null
Node head = new Node(4);
head.next = new Node(3);
head.next.next = new Node(2);
head.next.next.next = new Node(5);
head.next.next.next.next = new Node(1);
// Printing the list before sorting.
System.out.println("List before sorting - ");
printList(head);
// Calling the function to sort the list.
head = mergeSort(head);
// Printing the list after sorting.
System.out.println("List after sorting -");
printList(head);
}
}
```

**Output –**

```
List before sorting -
4 3 2 5 1
List after sorting -
1 2 3 4 5
```

### C++ Implementation

```
// C++ program to sort a linked list
// using the merge sort algorithm.
#include<bits/stdc++.h>
using namespace std;
// Node class
class Node{
public:
int val;
// Pointer to its next node
Node *next;
// Constructor
Node(int Val){
val = Val;
}
};
// Function to print the list
void printList(Node *head){
// Iterating while head is not nullptr.
while (head != nullptr){
cout << head->val << " ";
head = head->next;
}
cout << endl;
}
// Function to find the middle
// node of the linked list.
Node *findMiddle(Node *head){
// Base condition.
if (head == nullptr)
return head;
// Slow and fast pointers to
// iterate over the list.
// Fast pointer will take 2 steps
// at a time while slow pointer will
// take 1 step at a time.
Node *slow = head, *fast = head;
// Iterating while we have reached
// last or second last node of the list.
while (fast->next != nullptr && fast->next->next != nullptr){
fast = fast->next->next;
slow = slow->next;
}
// Node pointed by the slow pointer is the middle
// node of the list.
return slow;
}
// Function to merge two already sorted lists.
Node *mergeSorted(Node *left, Node *right){
// Base cases to check if either of
// the list provided is empty.
if (left == nullptr)
return right;
if (right == nullptr)
return left;
// Dummy node to hold the answer.
Node *dummy = new Node(-1);
// Declaring another variable 'node'
// to iterate further
Node *node = dummy;
// Iterating while both pointers
// are not null
while (left != nullptr && right != nullptr){
// If left's val is smaller than or
// equal to right's val.
if (left->val <= right->val){
// Assign left to node's next.
node->next = left;
// Move left to its next node.
left = left->next;
}
// Otherwise left's val is greater
// than right's val.
else{
// Assign right to node's next.
node->next = right;
// Move right to its next.
right = right->next;
}
// Moving node to its next node.
node = node->next;
}
// Iterating while left is not null.
while (left != nullptr){
// Assign left to node's next.
node->next = left;
// Move left to its next node.
left = left->next;
// Moving node to its next node.
node = node->next;
}
// Iterating while right is not null.
while (right != nullptr){
// Assign right to node's next.
node->next = right;
// Move right to its next.
right = right->next;
// Moving node to its next node.
node = node->next;
}
// Returning dummy's next as our answer.
return dummy->next;
}
// Function to sort the list.
Node *mergeSort(Node *head){
// Base condition to check if the head
// itself is nullptr or the list consists of
// only a single node.
if (head == nullptr || head->next == nullptr){
return head;
}
// Finding the middle node of the list.
Node *mid = findMiddle(head);
// Finding the next node of the middle node.
Node *nextToMid = mid->next;
// Breaking the list into two halves.
mid->next = nullptr;
// Recurring for the left and the right
// halves obtained.
Node *left = mergeSort(head);
Node *right = mergeSort(nextToMid);
// Merging the already sorted left
// and right part of the linked list.
Node *res = mergeSorted(left, right);
// Returning the result.
return res;
}
int main(){
// Constructing the following linked list.
// 4 --> 3 --> 2 --> 5 --> 1 --> nullptr
Node *head = new Node(4);
head->next = new Node(3);
head->next->next = new Node(2);
head->next->next->next = new Node(5);
head->next->next->next->next = new Node(1);
// Printing the list before sorting.
cout << "List before sorting - " << endl;
printList(head);
// Calling the function to sort the list.
head = mergeSort(head);
// Printing the list after sorting.
cout << "List after sorting -" << endl;
printList(head);
return 0;
}
```

**Output –**

```
List before sorting -
4 3 2 5 1
List after sorting -
1 2 3 4 5
```

### Python Implementation

```
# Python program to sort a linked list
# using the merge sort algorithm.
class Node:
# Constructor
def __init__(self, val):
self.val = val
self.next = None
# Function to print the list
def printList(head):
# Iterating while head is not None.
while (head != None):
print(head.val, end = " ")
head = head.next
print()
# Function to find the middle
# node of the linked list.
def findMiddle(head):
# Base condition.
if (head == None):
return head
# Slow and fast pointers to
# iterate over the list.
# Fast pointer will take 2 steps
# at a time while slow pointer will
# take 1 step at a time.
slow, fast = head, head
# Iterating while we have reached
# last or second last node of the list.
while (fast.next != None and fast.next.next != None):
fast = fast.next.next
slow = slow.next
# Node pointed by the slow pointer is the middle
# node of the list.
return slow
# Function to merge two already sorted lists.
def mergeSorted(left, right):
# Base cases to check if either of
# the list provided is empty.
if (left == None):
return right
if (right == None):
return left
# Dummy node to hold the answer.
dummy = Node(-1)
# Declaring another variable 'node'
# to iterate further
node = dummy
# Iterating while both pointers
# are not null
while (left != None and right != None):
# If left's val is smaller than or
# equal to right's val.
if (left.val <= right.val):
# Assign left to node's next.
node.next = left
# Move left to its next node.
left = left.next
# Otherwise left's val is greater
# than right's val.
else:
# Assign right to node's next.
node.next = right
# Move right to its next.
right = right.next
# Moving node to its next node.
node = node.next
# Iterating while left is not null.
while (left != None):
# Assign left to node's next.
node.next = left
# Move left to its next node.
left = left.next
# Moving node to its next node.
node = node.next
# Iterating while right is not null.
while (right != None):
# Assign right to node's next.
node.next = right
# Move right to its next.
right = right.next
# Moving node to its next node.
node = node.next
# Returning dummy's next as our answer.
return dummy.next
# Function to sort the list.
def mergeSort(head):
# Base condition to check if head
# itself is None or list consists of
# only a single node.
if (head == None or head.next == None):
return head
# Finding the middle node of the list.
mid = findMiddle(head)
# Finding the next node of the middle node.
nextToMid = mid.next
# Breaking the list into two halves.
mid.next = None
# Recurring for the left and the right
# halves obtained.
left = mergeSort(head)
right = mergeSort(nextToMid)
# Merging the already sorted left
# and right part of the linked list.
res = mergeSorted(left, right)
# Returning the result.
return res
# Constructing the following linked list.
# 4 --> 3 --> 2 --> 5 --> 1 --> None
head = Node(4)
head.next = Node(3)
head.next.next = Node(2)
head.next.next.next = Node(5)
head.next.next.next.next = Node(1)
# Printing the list before sorting.
print("List before sorting - ")
printList(head)
# Calling the function to sort the list.
head = mergeSort(head)
# Printing the list after sorting.
print("List after sorting -")
printList(head)
```

**Output –**

```
List before sorting -
4 3 2 5 1
List after sorting -
1 2 3 4 5
```

### Complexity Analysis

**Time Complexity –**Again, at each iteration we are dividing the list into two halves and in each step, we are merging the divided parts. Since the merging step requires $O(n)$ time and there are $O(\log_2{n})$ iterations, therefore, the overall time complexity is $O(n\log_2{n})$.**Space Complexity –**Since the`mergeSort`

function is a recursive function that requires $O(\log_2{n})$ recursive stack space, therefore the overall space complexity is $O(\log_2{n})$.

## Conclusion

`Merge sort`

is a divide and conquer algorithm whose worst case runtime is $O(n\log_2{n})$, where $n$ is the size of the list/array.- Accessing a random element is an $O(n)$ task in the case of a linked list that is why other efficient algorithms like
`quicksort`

,`heapsort`

, etc. perform poorly if applied on a linked list. - Merge sort does not access random elements and hence it wins over other sorting algorithms to sort a linked list.
- Merge sort requires $O(n\log_2{n})$ time and $O(\log_2{n})$ space to sort a linked list of $n$ nodes.

## FAQ

Q. **Why Other Sorting Algorithms are Inefficient on Linked Lists?**

A. Let’s try to understand this using an example. For example let the list be –

2 –> 3 –> 1 –> 5 –> 4 –> null

And we have **access only to the head node of the list** therefore if we use any other algorithm (say `quickSort`

) then we need to access some random elements many times.

Since we have access to the head node only therefore it would require $O(n)$ time just to access nodes.

In other words, it requires $O(1)$ time to access `a[k]`

in an array while to access the $k^{th}$ element of the list it requires $O(k)$ time.