C++ Linked Lists Explained

As a software developer, you’ll often work with lists—essential data structures for storing elements of the same type. In C++, lists differ from vectors because their data isn’t stored in contiguous memory. This difference has major implications for operations like finding or inserting elements. Let’s dive into these differences to help you better understand some fundamental programming concepts.

Understanding C++ Linked Lists

Before exploring linked lists, let’s compare them to a closely related data structure: the vector. Vectors store elements in contiguous memory, allowing fast data access. For example, finding the length of a vector is as simple as subtracting the first element’s address from the last. However, this adjacency in memory means that manipulating one part of the vector requires shifting other elements, which can be costly. That’s where linked lists come in.

What is a C++ Linked List?

A linked list is a more complex data structure than a vector. Each element in a linked list consists of the data itself and one or more pointers. A pointer is a variable that holds a memory address. In a singly linked list, each element points to the next one. In a doubly linked list, each element has pointers to both the previous and next elements. By default, C++ uses doubly linked lists, as seen in the C++ Standard Library.

To create a list in C++:

std::list<int> fibonacci = {0, 1, 1, 2, 3, 5, 8};

When defining a list, specify the data type in angle brackets (< >), and all elements must be of the same type.

Linked List Operations

Think of a linked list as a chain of elements. This structure allows you to manipulate it more dynamically than a vector. When inserting or deleting an element, only the directly connected elements need to be adjusted by updating the pointers. In contrast, manipulating a vector is like shifting items in an egg carton—everything needs to be rearranged to maintain order.

Inserting an Element

Here’s how to insert an element at the beginning of a linked list:

#include <iostream>
#include <list>
using namespace std;

int main() {
  list<int> fibo = {1, 1, 2, 3, 5, 8};  // create a Fibonacci sequence without zero

  fibo.push_front(0);  // insert 0 at the beginning

  for (int n : fibo) {
    cout << n << ' ';
  }
}

Output:

0 1 1 2 3 5 8

To append an element to the end of the list, use push_back.

Removing an Element

You can easily remove elements by value. In this example, you’ll delete elements with a value of 1 from the Fibonacci sequence:

#include <iostream>
#include <list>
using namespace std;

int main () {
  list<int> fibo = {0, 1, 1, 2, 3, 5, 8};

  fibo.remove(1);  // remove all elements with value 1

  for (int n : fibo) {
    cout << n << ' ';
  }
}

Output:

0 2 3 5 8

This removes all instances of the value. If you need to target a specific element, use an iterator.

Deleting by Position with an Iterator

An iterator points to the address of the element you want to erase:

#include <iostream>
#include <list>
using namespace std;

int main () {
  list<int> fibo = {0, 1, 1, 2, 3, 5, 8};
  list<int>::iterator it;

  it = fibo.begin();  // point the iterator to the start
  ++it;               // move the iterator one element forward
  fibo.erase(it);     // erase the element the iterator points to

  for (int n : fibo) {
    cout << n << ' ';
  }
}

Output:

0 1 2 3 5 8

Inserting an Element by Position

You can also use an iterator to insert an element at a specific position:

include

include

using namespace std;

int main () {
list fibo = {0, 1, 2, 3, 5, 8};
list::iterator it;

it = fibo.begin(); // point the iterator to the start
++it; // move one element forward
fibo.insert(it, 1); // insert 1 at the current position

for (int n : fibo) {
cout << n << ' ';
}
}`

Output:

0 1 1 2 3 5 8

Reversing the List

To print the Fibonacci sequence in reverse, simply use reverse on a doubly linked list:

`

include

include

using namespace std;

int main() {
list fibo = {0, 1, 1, 2, 3, 5, 8};

fibo.reverse(); // reverse the list

for (int n : fibo) {
cout << n << ' ';
}
}
`

Output:

8 5 3 2 1 1 0

When Not to Use Linked Lists

If you need to frequently access elements, such as with indexing, vectors are a better option. Linked lists, while flexible, take longer to compute because their elements aren’t stored in contiguous memory. To access an element, a linked list must traverse each node, which is computationally expensive.

Lists vs. Vectors

So when should you use lists, and when should you use vectors? It’s not always as simple as the theory suggests. Even for tasks involving a lot of insertion and deletion—actions typically suited for linked lists—a vector might perform better in some cases. Bjarne Stroustrup, the creator of C++, found that vectors outperform linked lists even when working with collections of over half a million elements. The takeaway: deciding between these data structures often requires empirical evidence.

Further Reading

To explore more about linked lists, check out the C++ specifications or find a manual implementation of a doubly linked list for deeper insights.

Comments

[Benjamin Stoneking]

Good refresher for me
List pros:

• Size constraints are more flexible
• Adding just one element does not require an expensive memory copy.
• Removing is likewise the same
• Adding to the front or back is fast and easy

List Cons:

• Non contiguous memory allocation means slower iterations
• Insertions in the middle require iteration and can be costly

Vector pros:

• Contiguous memory means faster read/write access
• Accessing by index
• More flexible than a standard c array

Vector cons:

• Rigid memory footprint. If you need to hold more elements than you currently have space, you must resize it and thus incur and expensive memory reallocation and copy
• Removal, insertion or shuffling of elements is expensive requiring expensive move operations or resizing.

Lots of things to consider when choosing this kind of data structure:

• Do you know how many elements you will need to hold for the duration of your program?
• Do you need to iterate often?
• Will you be moving values within your structure?
• Will you often iterate?
• Will you reorganize or sort your data?

It can be challenging to know which to use especially if you're finding that you need features from both types.

[Paul J. Lucas]

Your first example of creating a list is wrong. The list values come after an = after the name.