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

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

#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)