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:
- list() - constructor with initialization list for head and cursor pointing to the current element.
- prepend() - to insert a list element before the given element.
- add() - to append a list element at the end of the list.
- get_element() - to return the current data.
- advance() - to move the cursor to the next list element.
- print() - to print list elements.
The list class two private members:
- head - pointer to the first list_element.
- 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:
Ph.D. / Golden Gate Ave, San Francisco / Seoul National Univ / Carnegie Mellon / UC Berkeley / DevOps / Deep Learning / Visualization