A linked list will store a collection of "nodes".
A linked list data structure is represented as a chain of nodes chained/connected to each other. Each node has it's own data and a reference to the next node, which in turn has it's own data.
Implementation
Linked lists are used to represent:
- Stacks
- Queues
- Graphs
The 3 types of Linked Lists
Singly Linked List
A Single Linked List Data Structure will have nodes that have:
- Data
- Address which points to the next node
The last node will point to "null".
Operations on a linked list include:
- Insertion
- Deletion
- Traversal
You can implement a Linked List in C++ through structures and pointers:
//create a singly linked list //use keyword struct //The structure of the 1st node will be: //the first data member/ will be an integer // the second member of the node will be a node pointer called next struct Node { int data; struct Node *next; }; So if you have access to the first node, which contains the address to the 2nd node, which in turn contains the address of the 3rd node and so on - you have access to all the nodes in a singly linked list.
Let's have a look at the implementation of a singly linked list in C++
#include <iostream> using namespace std; //Declare Node structure template/blueprint //a node consists of an integer variable called num // and the 2nd part of the node is a pointer called *next struct Node{ int num; Node *next; }; //Declare starting (Head) node pointer to be NULL struct Node *head=NULL; //Insert node at start /* function insertNode takes an integer "n" as an arugment/paramter using struct Node create a newNode pointer which is = a new Node the newNode's data part (num ) is = the "n" parameter the newNode's next pointer points to Head and HEAD not is not null but instead the newNode */ void insertNode(int n){ struct Node *newNode=new Node; newNode->num=n; newNode->next=head; head=newNode; } //Traverse the list and cout all nodes /* #include <iostream> using namespace std; /*Declare Node structure template/blueprint a node consists of an integer variable called num and the 2nd part of the node is a pointer called *next which points to the next NODE */ struct Node{ int num; Node *next; }; //Declare starting (Head) node pointer to be NULL struct Node *head=NULL; //Insert node at start /* function insertNode takes an integer "n" as an arugment/paramter using struct Node create a newNode pointer which is = a new Node using the "new" keyword the arrow operator -> allows you to access elements in a structure the newNode's data part (num ) is pointing to the num part of the node which is = the "n" parameter Access the next part of a Node and assign it to be the head of the newNode and HEAD not is not null but instead the newNode */ void insertNode(int n){ struct Node *newNode =new Node; newNode->num=n; newNode->next=head; head=newNode; } //Traverse the list and cout all nodes /* If the head is === Null then let the user know that the list is empty and exit function else the *temp pointer = head and while the *temp pointer is not == NULL cout the data part of temp pointer and then temp is now = to the next temp pointer */ void display(){ if(head==NULL){ cout<<"List is empty!"<<endl; return; } struct Node *temp=head; while(temp!=NULL){ cout<<temp->num<<" "; temp=temp->next; } cout<<endl; } //delete node from start void deleteItem(){ if(head==NULL){ cout<<"List is empty!"<<endl; return; } cout<<head->num<<" is removed."<<endl; head=head->next; } int main(){ cout<<"<---- Singly Linked List ----->" <<endl; insertNode(1); insertNode(2); insertNode(3); deleteItem(); display(); return 0; } 
Top comments (0)