Linked String in C++ || PART 1 || C++ Class

What is a Linked String?

Linked String is a sort of array but it differs from array as it has nodes and each nodes points to the next element. A linked string can be both, Singly-Pointed (points to the node next to it) and Doubly-Pointed (points to the previous and next node). Unlike array, the elements in the linked string are not stored consecutively, rather nodes maybe placed at different addresses in the memory. 

In an array, the elements are stored consecutively i.e. they are placed in consecutive memory address e.g. we have an array [1, 2, 3, 4], now the first element 1 一 let's assume 一 is stored at address 205 then undoubtedly the next element 2 will be stored on address 206, similarly 3 on 207 and 4 on 208. 

On the other hand, if we have a linked list that contains [1, 2, 3, 4], the elements may not be at consecutive address spaces. For instance, element 1 maybe stored at address 125 while element 2 at address 20, element 3 at address 750 and element 4 at address 342.

Now, how do we make it possible to keep track of which nodes come after the other, which is the first or the last? Because for sure, when we print, it prints in the sequence we inserted i.e.  1, 2, 3, 4. This is done through Nodes. 

What is a Node?

A node is a struct which contains the data and a pointer. Think of it like a box having two objects within it. The data is an elements of Data Type like int, char, double, string or anything else. While the pointer is to the next node so that we know which node comes after the current one. (In case of Singly-linked list, there is only one pointer : next, but in Doubly-linked list, there are 2 pointers : next and previous) The struct's code will be:

Template <typename T>

struct Node

{

T data;

Node* next;   //remember! The type of the pointer is Node as it points to a Node: Next node!

};

But we also need to have pointers to the first and last node; Head and Tail nodes respectively. These pointers are private members of our Linked List class. I will illustrate here with a singly linked list class for characters. 

class LinkedList

{

private:

Node* head, *tail;   

int size;   //currently number of nodes/elements in the list

}

Let's take previous example where we have a singly linked list that contains [1,2,3,4,5]. 

• A Box depicts a Node
• The text in Orange shows the data within the node
• The Blue box inside node box shows the Pointer of type node and the purple colored text inside it shows the address of the next pointer saved in it
• On the top of each box, the address in dark Blue shows the address on which that node is stored

Now in the image, you can see, that the head is also a node that contains address of the first node i.e. at 245 containing element 1. And then each node contains the data (the element of type char in this case) and the pointer of type node* that points (shows in green color) to the next node i.e. contains the address of the next node. The last node containing 5 has no node next to it so we set its next pointer to Null. And then we make our tail pointer point to the last node i.e. the one containing element 5. 

In the next post, I will share the code for this class plus some additional functions. Stay tuned! 😊

Thank you for reading! ^^

NEXT POST >> Linked String in C++ || PART 2 || C++ Class