Skip to main content

Linked List C++

Must Know​

  • pointer
    • declaration: int* ptr
    • dereferncing pointer/ accessing value: *ptr
  • stuct
    • struct member selections
      • member selection operator: .
      • -> arrow operator: (*ptr).memberVar
  • Constructor
    • declaring Parameter and Default Constructors of short style: StructName(/* Parameters or No Paramters*/) : variable{valueOfvariable} {}

Linked List​

note

A node in a singly linked list should have two attributes: val and next.

  • val is the value of the current node
  • next is a pointer to the next node.
Node -- only the Node here
struct Node
{
    int val;    /* int is '4 bytes' */
    Node* next; // stores address of the 'next Node' : 'next' relative to the 'current Node with value "val" '
    /* here pointer is of type int* : 'int*' pinter is '4 bytes' */

    Node(int x) : val(x), next(nullptr) {} // 'Paramter Constructor' of short style
                                           /* Refer to  "Constructors" page of my Notes */

    /* so, size of '1 Node' on memory is (4+4 = 8 bytes) */
};
LinkedList -- all the operations of LinkedList here
struct LinkedList
{
    Node* head = nullptr;
    Node* tail = nullptr;
    int size = 0;

    void addAtHead(int val)
    {
        Node* newNode = new Node(val);
        newNode->next = head;
        head = newNode;
        if (size == 0)
            tail = newNode;
        // cout << "Added at head " << val << endl;
        // linked_list_print();
        size++;
    }

    void linked_list_print(Node* node)
    { // printing linked_list
        Node* tmp = node;

        while (tmp != nullptr)
        {
            cout << tmp->val << " "; // (*tmp).val
            tmp = tmp->next;         // (*tmp).next   /* next is a ptr, tmp is also a pointer */
        }
    }

};
calling the 
int main()
{
    LinkedList *obj = new LinkedList();

    obj->add_at_Head(55);
    obj->add_at_Head(77);
    obj->add_at_Head(1022);

    obj->linked_list_traversal(obj->head); /* `(*obj).((*obj).head)` */ // giving 'head pointer' value to the  "` void linked_list_print(Node* node) `"

    cerr << obj->head->val;  // printing only the 'val' of "head"
    /* ⏫ to access [val] variable of "[head] whcih is ptr of type [struct Node] " and [head] itself is inside [struct LinkedList] */

}d
note

to access [val] variable of "[head] whcih is ptr of type [struct Node] " and [head] itself is inside [struct LinkedList]

    cout << obj->head->val;

Singly Linked List​

add at Head​

   void addAtHead(int val)
    {
        Node* newNode = new Node(val);
        newNode->next = head;
        head = newNode;
        if (size == 0) {
            tail = newNode; /* in empty LiskedList the  `only 1 node` is both 'head' and 'tail' */
        }
        size++;
    }

  • newNode is the node which is going to be the new head
  • But newNode only has the val = val & next = NULL
    • as the next = NULL and we want the newNode to be before the current head, so: newNode->next = head; we give new head as the next of newNode
  • Now the newNode has values: val = val & next = head. And so this node is complete and ready to become the new head as the current head's is already the next of newNode
    • head = newNode;

add at Tail​

    void add_at_Tail(int val)
    {
        if (size == 0)
        {
            addAtHead(val); // If size=0 then there are nodes, so, tail->next is not possible as is used below
            /* adding to head because if sizxe is 0 then both head and tail have just one common node */
            return;
        }
        Node *newNode = new Node(val);
        tail->next = newNode;
        tail = newNode;
        if (size == 1)
        {
            head = newNode; /* in empty LiskedList the  `only 1 node` is both 'head' and 'tail' */
        }
    }
  • newNode is the node which is going to be the new head
  • But newNode only has the val = val & next = NULL
    • as the next = NULL and we want the newNode to be new tail, as tail should always be the last node with its next = NULL, so we add the newNode as the next of current tail: tail->next = newNode; tail = newNode;
    • now our current tail's next is not NULL, but our newNode which is at the next of current tail has next=NULL therefore we assignt the newNode as the new tail: tail = newNode;

add at index​

caution

in Singly Linked List if I have to access the node at index - 1, then I can use the current node as next of the beforeIndexNode i.e. I use the node which is before the index i.e. index - 1 and then access the current node at its beforeIndexNode->next

info
    void add_at_Index(int index, int val)
    {
        Node *newNode = new Node(val);

        Node *beforeIndexNode = head; // node at (index - 1)
        // we want the `index-1` node to be able to add the `newNode` as the `next` of this `index-1` node so that our `newNode` becomes the `indexNode`

        for (int i = 1; i <= (index - 1); i++) // ⚠️ (index - 1) is the node which is before the indexNode;    /* `i` starts with "1" as   '0' is already the head */
        /* ⚠️starting from `0` so that `beforeIndexNode` starts with head[as head is already at 0] and then `beforeIndexNode->next` will be pointing to the exact index and thus makes it easier for us to understand */
        /*  We do this so that we can access the `beforeIndexNode` & also we will be making  `newNode` as (newNode = beforeIndexNode->next) */
        {
            // `beforeIndexNode->next` means the `indexNode` where we want to add the 'newNode'
            beforeIndexNode = beforeIndexNode->next; /* beforeIndex is actually (index-2) but then `beforeIndex`is getting updated to `beforeIndex->next` here */
            /* ⚠️⚠️⚠️⚠️ there is NO 'i=0' as its `HEAD` so,  beforeIndexNode would become (beforeIndexNode->next)=1 which we don't want */
            // i=1 ⇢⇢  beforeIndexNode=0 ⇢⇢  (beforeIndexNode->next)=1
            // i=2 ⇢⇢  beforeIndexNode=1 ⇢⇢  (beforeIndexNode->next)=2  ...
        }

        /* ⭐⭐ "Reference to a Pointer": It DOES'T CHNAGE AS POINTER CHANGES ⭐⭐ */
        Node *&indexNode = beforeIndexNode->next; // MUST BE ADDED 'AFTER' FINDING THE 'beforeIndexNode'
        // getting the indexNode by `beforeIndexNode->next`
        // ❌❌ if added before the value of `beforeIndexNode` then will be wrong as DOES'NT UPDATE AS POINTER CHANGES

        newNode->next = indexNode; // Node *&indexNode = (beforeIndexNode->next)
        indexNode = newNode;       // Node *&indexNode = (beforeIndexNode->next)
    }

  • Variables used:

    • newNode: the node which is going to be inserted at that particular index
    • beforeIndexNode: It is node at index - 1
    • indexNode: "Reference to a Pointer" declared as Node*& indexNode = beforeIndexNode->next;: just make it easier to use beforeIndexNode->next

  • First Step: newNode has the next = NULL, so we will have to assign the node which was previously at the given index : newNode->next = indexNode;
    • Now, our new is currently linked to the node which was previously at the index position

  • Next Step is to add this newNode at the given index i.e. updating the indexNode
    • indexNode = newNode;: here indexNode is the node at given index. Therefore, we are assigning newNode to the node at index which is indexNode

Doubly Linked List​

note

A node in a doubly linked list should have three attributes: val, next and prev.

  • val is the value of the current node
  • next is a pointer to the next node.
  • prev to indicate the previous node in the linked list.