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)