Data Structure: Arrays and Lists (II)

Programming with C++

In the previous post, we talked about what arrays are and how they work. Here, we will go further and learn about lists!

Source: Unsplash

A list can be singly-linked (working forward) or doubly-linked (working bidirectional).

A singly-linked list

A singly-linked list only works in one direction, much like an array but with non-contiguous data storage.

A singly-linked list. The blue boxes represent the data elements and the purple boxes represent the corresponding memory locations.

Time complexity of a singly-linked list

1. Access: Accessing a data element in a linked list always starts from the beginning of the list. We then traverse through the pointers to the element of interest. This operation is of O(n).
2. Insertion/Deletion: With pointers, insertion/deletion at particular point is convenient in singly-linked list as we only need to change the pointer of the previous node. Therefore, this operation is of O(1).

Insertion to a singly-linked list. Note that the orange-shaded Pointer is the only pointer we need to change for this operation. Therefore, this is an O(1) operation.

A doubly-linked list

A doubly-linked list, on the other hand, can work in two directions, forward and behind. It offers flexibility in data manipulation but also requires larger memory to store.

A doubly-linked list. Two pointers, head and tail accompany one data element.

Time complexity of a doubly-linked list

The time complexity of doubly-linked lists is mostly the same as singly-linked lists. Note that when inserting/deleting an element, both directions are possible. For example, a singly-linked list can only insert data after the first element while one can add data before the first element in a doubly-linked list.

This will be better realized with hands-on programming practice.

Programming with C++

Singly-linked lists

// we use std::forward_list container for singly-linked lists
#include <iostream>
#include <forward_list>
using namespace std;
int main()
{
forward_list<int> list1 = {5, 4, 6, 2};
forward_list<int> list2 = {7, 6, 1, 9};
// 1. add an element
list1.insert_after(list1.begin(), 8);
// add element 8 "after" the 0 index (begin) of the list1
// we cannot add before the first element in forward_list
// 2. sort a list
list1.sort();
list2.sort();
// 3. merge two lists
list1.merge(list2); // update list1
// 4. splice_after()
list1.splice_after(list1.begin(), list2);
// take list2 and insert after the position of "0/begin" of list1
// update list1
cout << "Size of list2 " << std::distance(list2.begin(), list2.end()) << endl;
// list2 be removed
// 5. unique()
forward_list<int> list1 = {5, 2, 4, 6, 2, 2, 2};
list1.unique();
// returns 5, 2, 4, 6, 2
// remove the last element of the consecutive sequence of the same values (cannot remove the others, which is a limitation)
forward_list<int> list1 = {5, 2, 4, 6, 2};
list1.unique(); // will not remove any 2 since they are not adjacent to each other
// 6. remove
list1.remove(2);
// remove all the elements of 2 in the list
// 7. remove_if: remove with conditions
list1.remove_if([](int n) { 
return n > 4;           
});
// remove elements that are >4
// 8. resize
list1.resize(2); // remove elements after index 1
list1.resize(6); // increase 0 elements at the end to the new size
// 9.
list1 = list2; 
// remove list1 and put the content of list2 to list1
// 10. print
for (auto &elm : list1)
{
cout << elm << endl;
}
return 0;
}

Doubly-linked lists

#include <iostream>
#include <string>
#include <list>
#include <vector>
using namespace std;
int main()
{
// 1. create a list that contains string elementslist<string> myStrings;
myStrings.push_back("Apple");
myStrings.push_front("Banana");
myStrings.push_back("Candy");
myStrings.push_back("Door");
// push_back (add behind) and push_front (add before) are available for doubly-linked lists
// 2. iterate over a list
list<string>::iterator itr;
for (itr = myStrings.begin(); itr != myStrings.end(); itr++)
{
cout << *itr << endl;
}
// 3. remove an element from the beginning/end of the list
myStrings.pop_front();
myStrings.pop_back();
// 4. remove an element with value from the list
list<string>::iterator itr;
itr = myStrings.begin();
while (*itr != "Bob")
{
itr++;
}
myStrings.erase(itr);
//5. insertion
list1.insert(next(list1.begin()), 0); 
// add 0 after the begin element list1.insert(next(list1.begin(), 2), 100); 
// add 100 after the position of begin +2
list1.insert(prev(list1.end()), 0);
// add 0 before the end element
list1.push_front(0);
// add 0 before the begin element
for (auto &elm : list1)
{
cout << elm << " ";
}
return 0;
}

Array, list, which one to use?

Before we decide on which data type to use, a few characteristics should be considered.

Direction

An array and a singly-linked list can only work forward. This may deem inconvenient, however, this could also be favorable when you do not want to overwrite past records.

A doubly-linked list offers flexibility in editing the data but also takes up more memory space as it needs two pointers for each data node.

Contiguousness

The main difference between an array and a list is how they store data. An array store data contiguously and therefore has the advantage of cache locality that offers faster data access. A list stores data in different memory locations with pointers that associate the data elements.

Comparison and summary of time complexity