C++ Tutorial - Linked List Basics - 2020

A linked list is a basic data structure where each item contains the information that we need to get to the next item.

The main advantage of linked lists over arrays is that the links provide us with the capability to rearrange the item efficiently. This flexibility is gained at the expense of quick access to any arbitrary item in the list, because the only way to access to an item in the list is to follow links from the beginning.

We can make linked list either as a struct or a class as shown below:

struct list_element
{
  list_element(int n = 0, list_element* ptr = 0):
    data(n), next(ptr) {};
  int data;
  list_element *next;
};

class list_element
{
public:
  list_element(int n = 0, list_element* ptr = 0):
    data(n), next(ptr) {};
  int data;
  list_element* next;
}

Both of the codes are equivalent.
We have two data members (data and next) and a constructor with initialization list. All of the members are public.

Here is the code for list class with the list element struct:

struct list_element
{
  list_element(int n = 0, list_element* ptr = 0):
    data(n), next(ptr) {};
  int data;
  list_element *next;
};

class list
{
public:
  list(list_element *h = 0, list_element *c = 0):head(h),cursor(c) {}
  void prepend(int n);  // add an element before head
  void add(int n);   // add an element at the end of the list
  int get_element() { return cursor->data;}
  void advance() { cursor = cursor->next; }
  void print();
private:
  list_element *head;
  list_element *cursor;
};

The class has 6 methods:

1. list() - constructor with initialization list for head and cursor pointing to the current element.
2. prepend() - to insert a list element before the given element.
3. add() - to append a list element at the end of the list.
4. get_element() - to return the current data.
5. advance() - to move the cursor to the next list element.
6. print() - to print list elements.

The list class two private members:

1. head - pointer to the first list_element.
2. cursor - pointer to the current list_element.

Here is the implementation of the singly linked list:

#include <iostream>
using namespace std;

typedef struct list_element
{
  list_element(int n = 0, list_element* ptr = 0):
    data(n), next(ptr) {};
  int data;
  list_element *next;
} list_element;

class list
{
public:
  list(list_element *h = 0, list_element *c = 0):head(h),cursor(c) {}
  void prepend(int n);  // add an element before head
  void add(int n);   // add an element at the end of the list
  int get_element() { return cursor->data;}
  void advance() { cursor = cursor->next; }
  void print();
private:
  list_element *head;
  list_element *cursor;
};

void list::prepend(int n)
{
  // swap head with current head
  if(head) {
    head = cursor = new list_element(n, head);
  }
  // if empty list, make current element as head
  else
    head = new list_element(n, head);
}

void list::add(int n)
{
  if(head) {
    cursor = head;
    while(cursor) {
      // end of the list
      if(cursor->next == NULL) {
        cursor->next = new list_element(n);
        break;
      }
      // advance to the next element
      else
        advance();
    }
  }
  // no head, make head with current element
  else {
    head = new list_element(n);
  }
}

void list::print()
{
  if(head)
  {
    cursor = head;
    while(cursor) {
      cout << get_element() << " ";
      advance();
    }
  }
  else
    cout << "Empty list!" << endl;
}

int main()
{
  list myList(new list_element(1));
  myList.add(2);
  myList.add(3);
  myList.prepend(0);
  myList.add(4);
  myList.prepend(-1);
  myList.add(5);
  myList.print();
  return 0;
}

Output:

-1 0 1 2 3 4 5

For more complete implementation, we need a descturtor. Also, for convenience, we may want to construct the list from an array. Here is a new code with those two member functions:

#include <iostream>
using namespace std;

typedef struct list_element
{
  list_element(int n = 0, list_element* ptr = 0):
    data(n), next(ptr) {};
  int data;
  list_element *next;
} list_element;


class list
{
public:
  list(list_element *h = 0, list_element *c = 0):head(h),cursor(c)
  { cout << "default constructor\n"; }

  list(const int *arr, int sz); // move elements from an array
  ~list(); // destructor

  void prepend(int n);  // add an element before head
  void add(int n);   // add an element at the end of the list
  int get_element() { return cursor->data;}
  void advance() { cursor = cursor->next; }
  void print();
private:
  list_element *head;
  list_element *cursor;
};

// constructor : move elements from an array
list::list(const int array[], int sz)
{
  head = cursor = 0;

  // populate the list element using add()
  for(int i = 0; i < sz; ++i) {
    add(array[i]);
  }
}

// destructor
list::~list()
{
  for(cursor = head; cursor != 0;) {
    cursor = head->next;
    delete head;
    head = cursor;
  }
}

void list::prepend(int n)
{
  // swap head with current head
  if(head) {
    head = cursor = new list_element(n, head);
  }
  // if empty list, make current element as head
  else
    head = new list_element(n, head);
}

void list::add(int n)
{
  if(head) {
    cursor = head;
    while(cursor) {
      // end of the list
      if(cursor->next == NULL) {
        cursor->next = new list_element(n);
        break;
      }
      // advance to the next element
      else
        advance();
    }
  }
  // no head, make head with current element
  else {
    head = new list_element(n);
  }
}

void list::print()
{
  if(head)
  {
    cursor = head;
    while(cursor) {
      cout << get_element() << " ";
      advance();
    }
  }
  else
    cout << "Empty list!" << endl;
}

int main()
{
  int arr[] = {1, 2, 3, 4, 5};
  list myList(arr,5);
  myList.add(6);
  myList.prepend(0);
  myList.print();
  return 0;
}

Output:

0 1 2 3 4 5 6

There are more sample codes for linked list:

1. Linked List Examples
2. Linked List - Quiz