Note: use the github provided TOC for navigaing.
//defining the node
class node(){
public:
int data;
node* next;
//constructor
node(int d){
data = d;
next = NULL;
}
};
I would like to mention three key points of LL own implementation,
node* head = new node(d)
we are actually storing the address of the newly created node. Everytime when we will use node* temp = node(d)
it will give the address of that created node.new node(d)
and node(d)
are different, node(d)
will crete a node in static memory, bcoz of this fact we wont be able to find this node next time we try to update it. And if we use new node(d)
then it will be using dynamic memory to allocate the node, so no faire of missing the created node.insert_head()
is simple, if the head passes in the function is NULL then create a node and give its address to head and return, else create a new node and assigned its address to it and update the head.node* abcd = new node(d)
, this means that address of the node box lies in the abcd pointer.
void insert_head(node*& head,int d){ //passing by reference
if(head == NULL){
head = new node(d); // creating node in dynamic memory
// which only returns the address of
// created node
return;
}
node *n = new node(d);
n->next = head;
head= n;
}
// driver code
int main(){
node* head = NULL;
insert_head(head,1);
insert_head(head,2);
print_ll(head); // prints-> 2, 1,
}
p
is equal to 0, or head == NULL
then perform insert_head
, if pis grater than or equal to length of the linkedlist then perform insert_tail
else, perform insert_middle
.
void insert_middle(node*&head,int data,int p){
if(p==0){
insert_head(head,data);
return;
}
else if(p>=length(head)){
insert_tail(head,data);
return;
}
else{
node*temp = head;
int jump = 1;
while(jump<=p-1){
temp = temp->next;
jump++;
}
node*n = new node(data);
n->next = temp->next;
temp->next = n;
}
return;
}
// search using iterative approach
bool search(node* head,int key){
node* temp = head;
while(temp->next==NULL){
if(head->data == key){
return true;
}
}
return false;
}
// search: search using recursion where we return the address of the desired key
node* search_recursion(node*head,int key){
if(head==NULL){
return NULL;
}
if(head->data==key){
return head;
}
else{
return search(head->next,key);
}
}
// search: search using recursion, returns the presence of the key using bool
bool search_recursion_bool(node*head,int key){
if(head==NULL){
return false;
}
if(head->data==key){
return true;
}
else{
return search(head->next,key);
}
}
void insert_tail(node*&head,int data){
if(head==NULL){
head = new node(data);
}
else{
node*temp = head;
while(temp->next!=NULL){
temp = temp->next;
}
temp->next = new node(data);
}
}
void delete_head(node* head){
node* temp = head->next;
delete head;
head = temp;
}
// printing the ll
void print_ll(node* head){ // at the print time we dont pass by reference
while(head!=NULL){
cout<<head->data<<", ";
head = head->next;
}
cout<<endl;
}
int length(node *head){
int len=0;
while(head){
len++;
head = head->next;
}
return len;
}
//
node* take_input(){
int d;
cin>>d; // taking the data
node* head = NULL; // creating the head pointer
while(d!=-1){ // - + untill user provides -1 as the input we ill keep taking input from user
insert_head(head,d); // | and insert in the head(we can use other insert operations too)
cin>>d; // | and take input from the user, which will eventually update d.
} // - +
return head; // we return head as we are not taking head in the function input.
}
// driver function
int main(){
node* head = take_input();
print_ll(head);
}
// take input from input.txt
node* take_input_txt(){
int d;
node* head = NULL;
while(cin>>d){
insert_head(head,d);
}
return head;
}
bool detect_cycle(node* head){
node* slow = head;
node* fast = head;
while(fast!=NULL && fast->next !=NULL){ // we keep the loop on untill then fast is not equal to NULL and fast-> != NULL(this is because we are doing fast->next->next in the next line)
fast = fast->next->next;
slow = slow->next;
if(fast==slow){
return true;
}
}
return false;
}
<img src="../../imgs/create_cycle.png", width="400">
p->next = NULL
. we know,
D_fast = 2 * D_slow
=> x+2y+z = 2* x + 2*y
=> x = z(proved)
Code explanation: https://youtu.be/Fj1ywT9ETQk
// head - Head pointer of the Linked List
// Return a boolean value indicating the presence of cycle
// If the cycle is present, modify the linked list to remove the cycle as well
bool floydCycleRemoval(node *head)
{
/* Code here */
node *slow = head;
node *fast = head;
while (fast != NULL && fast->next != NULL){
fast = fast->next->next;
slow = slow->next;
if (fast == slow) {
fast = head;
while(slow->next != fast->next)
{
slow = slow->next;
fast = fast->next;
}
slow->next=NULL; // here we do the 1st step(p->next = NULL) and at this position slow and fast at the same position, making changes in fast or slow will result the same.
return 1; // if it returns 1, it means its a circular linkedlist
}
}
return 0; // if it returns 0, it means its a circular linkedlist
}
Doubly linked list is similar to singly ll but it also points to the previous node, it has two boxes which stores the addtess of previous and next node and another box stores the data. It helps to interate over a linkedlist.
<img src="../../imgs/ll6.png"width="600">
<img src="../../imgs/ll7.png"width="600">
void insert(node*& head, int data){
node* n= new node(data);
node* temp = head;
n->next = head;
if(temp!=NULL){
while(temp-> next!=head){
temp = temp->next;
}
temp->next = n;
}
else{
n->next = n;
}
head = n;
}
void print(node*head){
node* temp = head;
while(temp->next!=head){
cout<<temp->data<<" ";
temp = temp->next;
}
cout<<temp->data<<endl;
return;
}
int main(){
node* head = NULL;
insert(head,3);
insert(head,4);
insert(head,5);
insert(head,6);
print(head);
}
<img src="../../imgs/ll8.png"width="600">
// find a node
node* search_node(node*head,int data){
node* temp = head;
while(temp->next!=head){
if(temp->data == data){
return temp;
}
temp = temp->next;
}
if(temp->data == data){
return temp;
}
return NULL;
}
void delete_node(node*&head,int data){
node* del = search_node(head,data)
if(del==NULL){
return;
}
//otherwise
if(head==del){
head = head->next;
}
node*temp = head;
//stop one step behind the node to be deleted
while(temp->next!=del){
temp = temp->next;
}
temp->next = del->next;
delete del;
}
int main(){
node* head = NULL;
insert(head,3);
insert(head,4);
insert(head,5);
insert(head,6);
delete_node(head,5);
print(head);
}
forward_list is singly linkedlist and normal list is actually doubly linkedlist
#include <list>
int main(){
// input in list
list<int> l;
list<int> l1{1,2,3,4,5};
list<string> l2{"apple","sony","hello"};
// push back pushes any elemt at the back
l2.push_back("vivo");
// reverse reverses the order
l2.reverse();
// this sorts the linkedlist
list.sort();
// front() helps to get the 1st element
cout<<l2.front()<<endl;
// pops out the 1st element from front
l2.pop_front();
// pushes at the front
l.push_front("oppo");
// get the back of ll
cout<<l2.back()<<endl;
// push any element at the back of the linked list
l2.pop_back();
// use iterator base loop to inerate through a ll
for (auto it=l2.begin();it!=l2.end();it++){
cout<<(*it)<<endl;
}
// again push back
l2.push_back("samsang")
l2.push_back("one plus")
// again remoev
l2.remove("oppo");
// for each loop for iterating through a ll
from(string s:l2){
cout<<s<<endl;
}
// erase one or more element
auto itr = l2.begin();
it++; // as direcr access does not work with ll, so we use this
// to get the next node
l2.erase(it); // erase any elemnt by passing the iterator
// again for each
from(string s:l2){
cout<<s<<endl;
}
//insert element in the list after 1st element
it = l2.begin();
it++;
// insert at the position(mentioned by the it, which is a iterator)
l2.insert(it,"nokia");
// again for each loop
from(string s:l2){
cout<<s<<endl;
}
}