Linked Lists in C++
How to insert Node at beginning of a Linked List
- Two Senerios
- List is Empty
- List isn’t Empty
#include<iostream>
using std::cout; using std::endl;
using std::cin;
struct Node{
int data;
Node* next;
};
Node* head = NULL; // Global Variable, can be accessed anywhere
void Insert(int x)
{
Node* temp = new Node();
temp->data = x;
temp->next = head;
head = temp;
}
void print()
{
// Print Linked Lists
Node* temp = head; // address of the head node pointing to the first node in the linked list
// Using a temp variable so we don't modify
cout << "List is: ";
while(temp != NULL)
{ // Iterate through
cout<<temp->data<<"->";
temp=temp->next;
}
cout<< endl;
}
int main()
{
cout << "How Many numbers? \n";
int n, i, x;
cin >> n;
for (i = 0; i <n; i++ ){
cout << "Enter the number \n";
cin >> x;
Insert(x);
print(); // Print out Current linked List
}
}
Lets say we want 5 Nodes and we want to insert the numbers 3,4,10,68, and 12
Output
How Many numbers?
5
Enter the number
3
List is: 3->
Enter the number
4
List is: 4->3->
Enter the number
10
List is: 10->4->3->
Enter the number
68
List is: 68->10->4->3->
Enter the number
12
List is: 12->68->10->4->3->
Linked List in C/C++ - Insert a node at nth position
- Insert Node at any postion in the linked list
#include<iostream>
using std::cout; using std::endl;
using std::cin;
struct Node{
int data;
Node* next;
};
Node* head = NULL; // Global Variable, can be accessed anywhere (Empty List)
void Insert(int data, int n)
{
Node* temp1 = new Node();
temp1->data = data;
temp1->next = NULL;
if (n == 1){
// Like Regular Insert at Begining Code
temp1->next = head;
head = temp1;
return; // Finish, exit
}
// Else, were inserting at another position other than Begining
Node* temp2 = head;
// Iterating Memory from Head (beginning of our Linked List)
for (int i = 0; i < n-2; i++ )
{
// Find the position ONE BEFORE where we want to insert
temp2 = temp2->next; // Store Address
}
temp1->next = temp2->next;
temp2->next = temp1;
}
void print()
{
Node* temp = head; // address of the head node
cout << "List is: ";
while(temp!=NULL){
cout<<temp->data<<"->";
temp=temp->next;
}
cout<< endl;
}
int main()
{
Insert(2,1); // List: 2
Insert(3,2); // List: 2, 3
print();
Insert(4,1); // List; 4,2,3
print();
Insert(5,2); // List: 4,5,2,3
print();
Insert(16,4); // List; 4,5,2,3,69
Insert(69,5); // List; 4,5,2,3,6
Insert(420,1);
print();
}
Output:
List is: 2->3->
List is: 4->2->3->
List is: 4->5->2->3->
List is: 420->4->5->2->16->69->3->
Linked List in C/C++ - Delete a node at nth position
- Insert Notes
#include<iostream>
using std::cout; using std::endl;
using std::cin;
struct Node{
int data;
Node* next;
};
Node* head = NULL; // Global Variable, can be accessed anywhere (Empty List)
void Insert(int data, int n)
{
Node* temp1 = new Node();
temp1->data = data;
temp1->next = NULL;
if (n == 1){
// Like Regular Insert at Begining Code
temp1->next = head;
head = temp1;
return; // Finish, exit
}
// Else, were inserting at another position other than Begining
Node* temp2 = head;
// Iterating Memory from Head (beginning of our Linked List)
for (int i = 0; i < n-2; i++ )
{
// Find the position ONE BEFORE where we want to insert
temp2 = temp2->next; // Store Address
}
temp1->next = temp2->next;
temp2->next = temp1;
}
void Delete(int n)
{
Node* temp1 = head;
if (n == 1)
{
head = temp1->next; // head now points to second node
delete(temp1); // Remove memory From HEAP
return; // after we execute
}
for (int i = 0; i < n-2; i++ )
{
temp1 = temp1->next;
}
Node* temp2 = temp1->next; // nth Node
temp1->next = temp2->next; // (n+1)th Node
delete(temp2); // Delete temp2
}
void print()
{
Node* temp = head; // address of the head node
cout << "List is: ";
while(temp!=NULL){
cout<<temp->data<<"->";
temp=temp->next;
}
cout<< endl;
}
int main()
{
Insert(2,1); // List: 2
Insert(3,2); // List: 2, 3
print();
Insert(4,1); // List; 4,2,3
print();
Insert(5,2); // List: 4,5,2,3
print();
Insert(16,4); // List; 4,5,2,3,69
Insert(69,5); // List; 4,5,2,3,6
Insert(420,1);
print();
// Lets try to delete
int position;
cout << "Enter a Position to Delete: ";
cin >> position;
Delete(position);
print();
}
Output
List is: 2->3->
List is: 4->2->3->
List is: 4->5->2->3->
List is: 420->4->5->2->16->69->3->
Enter a Position to Delete: 3
List is: 420->4->2->16->69->3->
(base) Devins-MBP-2:linked_lists devinpowers$ ./a.out
List is: 2->3->
List is: 4->2->3->
List is: 4->5->2->3->
List is: 420->4->5->2->16->69->3->
Enter a Position to Delete: 1
List is: 4->5->2->16->69->3->
Reverse Linked List (iterative)
#include<iostream>
using std::cout;
using std::endl;
using std::cin;
/*
Auther: Devin Powers
Project: Reverse a Linked List -iterative
Data: August 8th 2021
*/
struct Node{
int data;
Node* next;
};
Node* head;
void Insert(int x)
{
Node* temp = new Node(); // Create New Node to Insert
temp->data = x;
temp->next = head;
head = temp;
}
void print()
{
Node* temp= head; // address of the head node
cout << "List is: ";
while(temp!=NULL){
cout<<temp->data<<"->";
temp=temp->next;
}
cout<< endl;
}
void Reverse()
{
Node *current, *next, *previous;
current = head;
previous = NULL;
// Run loop
while (current != NULL)
{
next = current->next;
current->next = previous; // *(current).next
previous = current; // resetting previous pointers
current = next;
}
// When Current is = NULL
head = previous;
}
int main()
{
Insert(5);
Insert(6);
Insert(4);
Insert(2);
cout << "Before Reversing Linked List: " << endl;
print();
cout << "After Reversing Linked List: " << endl;
Reverse();
print();
}
Output:
Before Reversing Linked List:
List is: 2->4->6->5->
After Reversing Linked List:
List is: 5->6->4->2->
Print elements of a linked list in Forward and Reverse order using Recursion
#include<iostream>
using std::cout;
using std::endl;
struct Node{
int data;
Node* next;
};
Node* head=NULL;
void print_forward(Node* p)
{
// Using Recurison
if (p == NULL)
{
return; // Exit Condtion
}
cout << p->data << " -> "; // prints value in the node
print_forward(p->next); // Recusive Call
cout << endl;
}
void print_reverse(Node* p)
{
// Using Recursion
if (p == NULL)
{
return;
}
print_reverse(p->next); // Recursive Call
cout << p->data << " -> ";
}
void Insert(int x)
{
Node* temp = new Node(); // Create New Node to Insert
temp->data = x;
temp->next = head;
head = temp;
}
int main(){
head=NULL;
Insert(5);
Insert(6);
Insert(4);
Insert(2);
cout << "Print Linked List Forward (Recusion) " << endl;
print_forward(head);
cout << "Print Linked List Reverse (Recusion) " << endl;
print_reverse(head);
cout << endl;
}
Output:
Print Linked List Forward (Recusion)
2 -> 4 -> 6 -> 5 ->
Print Linked List Reverse (Recusion)
5 -> 6 -> 4 -> 2 ->
Reverse a linked list using Recursion
#include<iostream>
using std::cout;
using std::endl;
struct Node{
int data;
Node* next;
};
Node* head=NULL;
void Insert(int x)
{
Node* temp = new Node(); // Create New Node to Insert
temp->data = x;
temp->next = head;
head = temp;
}
void Reverse(Node* p)
{
if (p->next == NULL)
{
//Exit condition
head = p;
return;
}
Reverse(p->next);
Node* q = p->next;
q->next = p;
p->next = NULL;
}
void printLinkedList(){
Node* temp=head;
while(temp!=NULL){
cout<<temp->data<<"->";
temp=temp->next;
}
cout<< endl;
}
int main()
{
head=NULL;
Insert(5);
Insert(6);
Insert(4);
Insert(2);
cout << "Print Before Reversed " << endl;
printLinkedList();
Reverse(head);
cout << "Print Linked List" << endl;
printLinkedList();
}
Output:
Print Before Reversed
2->4->6->5->
Print Linked List
5->6->4->2->