A list can be implemented as

  • Arrays: statically allocated (Array) or dynamically allocated (ArrayList)
  • Linked Lists: dynamically allocated
    A list can be sorted or unsorted.

ArrayList

Also called Dynamic Array.

  • Element - Each item sotred in an array
  • Index - Each location of an element in an array (to identify the element)

LinkedList

It’s essentially just a sequence of elements, where each element links to the next element which links the next element.

This list consists of a number of nodes in which each node has a next pointer to the following element.

A linked list can contain pretty much any type of data, strings, characters, numbers, the elements can be unsorted or sorted, they can contain duplicate elements or all unique elements.

The link of the last node in the list is NULL, which indicates the end of the list.

Properties of LinkedList

A linked list is a data structure used for storing collections of data. A linked list has:

  • Successive elements are connected by pointers
  • Last element points to NULL
  • Can grow or shrink in size during execution of a program
  • Does not waste memory space, it allocates memory as list grows

Why use Linked List?

Advantage

  • Easy manipulation - insert and delete can be very quick
  • Simple sequential operations (e.g. searching, updating) are fast
  • Efficient use of memory - No need to pre-allocate a maximum size of required memory
  • Variations - Variable number of variable-size lists (Even Multi-dimensional lists)

Disadvantage

  • Slow to get n-th element
  • Take up additional memory space for the links
  • Accessing random parts of the list is slow. (need to walk sequentially)

What can a Linked List do?

Insert - inserts an element into the list

Delete - Removes and returns the specified position element from the list

Delete List - removes all elements of the list (disposes)

Count : returns the number of elements in the list

Find : find specified node from the list

Delaration

1
2
3
4
struct ListNode{
  int data;
  ListNode *next;
};

Insertion

Insertion into a singly-linked list has three cases:

  • Inserting a new node before the head (at the beginning)
  • Inserting a new node after the tail (at the end of the list)
  • Inserting a new node at the middle of the list (random location)

before the head

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <iostream>
using namespace std;

struct node{
    int data;
    node *next;
};

class linkedList{
    private:
        node *head, *tail; // 2 Nodes created
    public:
        linkedList(){
         //No value inside the nodes yet
         head = NULL;
         tail = NULL; 
        }
    
    //Insert From First
    void addNode(int value)
    {
        node *tmp = new node;
        tmp->data = value;
        tmp->next = NULL;

        if(head == NULL) //Generate 1st Node
        {
            //Note: 1st Node is not only head but also tail.
            head = tmp; 
            tail = tmp;
        }
        else
        {
            tail->next = tmp;
            tail = tail->next; //The newly added Node became tail
        }
        
    }

    void display()
    {
        node *tmp;
        tmp = head;
        while (tmp != NULL) //check if the element is no NULL.
        {
            cout << tmp->data << endl; //print the data.
            tmp = tmp->next;    //move to the next node.
        }
    }
};

int main()
{
    linkedList list;
    list.addNode(1);
    list.addNode(2);
    list.addNode(3);
    list.display();
    return 0;
}

Deletion

Deletion of a singly-linked list also has three cases:

  • Deleting the first node
  • Deleting the last node
  • Deleting an intermediate node.

Double LinkedList

A doubly linked list is just like a singly linked list but in addition to each elementhaving a link to the next element, each element also links the previous element.

Circular Lists

Doubly Circular Linked List

Comparison of Linked Lists with Arrays & Dynamic Arrays

Parameter Linked List Array Dynamic Array (Array List)
Indexing O(n) O(1) O(1)
Insertion / Deletion at beginning O(1) O(n) if array is not full (for shifting the elements) O(n)
Insertion at ending O(n) O(1) if array is not full O(1) if array is not full
O(n) if array is full
Deletion at ending O(n) O(1) O(n)
Insertion in middle O(n) O(n) if array is not full (for shifting the elements) O(n)
Deletion in middle O(n) O(n) if array is not full (for shifting the elements) O(n)
Wasted space O(n) (for pointers) 0 O(n)

Reference

A Comprehensive Guide To Singly Linked List Using C++

CS Dojo - Introduction to Linked Lists

HackerRank - Data Structures: Linked Lists

A list of all data structures