data structure

List data structure for beginners, a complete guide

In programming, there are many data structures. Data structures are ways of storing data optimally. In this article, I am going to describe the List data structure for beginners.

The List is a very essential and concept light data structure. It is a collection of elements or values. 

In this article, I am going to discuss the below topics.

  • A logical view of List data structure
  • Available operations on List
  • Cost of each operation (Time Complexity)

A logical view of List data structure

Programmatically, a List is nothing but values stored in contiguous memory locations where each location contains data of the same data type.

If we think of a real-life example then, a List can be anything, a list of names, a list of numbers or any similar type of data that we need to store in synchronous order.

The question is, why do we even use a list. We use a List for the following reasons.

  1. Store multiple elements of the same data type in a list.
  2. Access or read an element at a particular position in a list.
  3. Modify an element at a particular position in a list.

Available operations on List

As described above, the available operations on a list are the same with the options that a list provides us. Here is a list of possible operations that we can perform on a list.

  • Insert an element.
  • Count the number of elements.
  • Read an element at a position.
  • Modify an element at a position.
  • Remove an element at a position.

Cost of each operation (Time Complexity)

Cost of Inserting an element into a list data structure

Inserting an element in a list can be of two types

  1. Insert at the end of the list.
  2. Insert at a particular position in a list.

At the end of the list

If we talk about inserting an element at the end of a list, the time will always be constant. Hence, the worst time complexity of this operation would be O(1).

Insert at a particular position in a list

If we try to insert an element at any specific position then, we have to check how many elements are there, after that position in the list. Please see the example below.

| 32 | 100 | 53 | 41 | 11 | 58 | 72 | 22 | 9 |

Let suppose we want to insert an element at index 3 (41). Now, we have to shift all the elements, including the one from index 3 to one position right, to make space for the new element.

Once shifting operation completes, the list will look like below.

| 32 | 100 | 53 | --  | 41 | 11 | 58 | 72 | 22 | 9 |

And then, we can insert our new element in the empty position.

Now think, in the worst case if we had to insert the element at the beginning of the list then, we would move all the n number of elements.

So the worst-case time complexity for such operations would be O(n).

Cost of reading and modifying an element in a list data structure

If we have an index of the element then the reading or, an in-place modification will take a constant amount of time. So, the worst-case time complexity will be O(1).

Cost of removing an element from a list data structure

In case of removing an element from any given index, we will have to delete the element first. And then, we have to move all the elements after that position to one position left to fill up any empty spot in the list. Let’s look at the below example.

| 32 | 100 | 53 | 41 | 11 | 58 | 72 | 22 | 9 |

Let suppose we have to remove the element from index 2 (53). At first, we will remove the element from that position. And the list will look like below.

| 32 | 100 |   --  | 41 | 11 | 58 | 72 | 22 | 9 |

Then to fill up the empty place, we have to shift all the elements beginning from index 3 to one position left and, the list will look like below.

| 32 | 100 | 41 | 11 | 58 | 72 | 22 | 9 |

Now think, if we had to remove the first element then, all the remaining n elements would shift one position to the left. So the worst-case complexity of this operation is O(n).

Leave a Comment

ninety four − ninety =