llsetup.md

How to setup a Linked List:

1. Set the struct:

To set up the node, first, we must set up a struct:

struct node {
  int data;                                  // The data part that holds the general data for the node
  node* next;                                // The pointer part that is connecting this node with others
};

2. Define the class:

Next, we have to create a class for the list with public and private data members, and to address what belongs in them, the private should always hold the pointer to the head, and the public should hold the general functions that you call for the list such as insertions, deletions, counters, or prints:

class linkedList {
  private:
    node *head;                              // Pointer to the head
  
  public:
    list() { head = nullptr; }               // Default constructor
  
    void insertHead(int data);               // Insertion at the head
    void insertTail(int data);               // Insertion at the end
    void insertPos(int data, int pos);       // Insertion at the called position
  
    void removeHead();                       // Deletion at the head
    void removeTail();                       // Deletion at the end
    void removePos(int pos);                 // Deletion at the called position
  
    string printHead();                      // Printing the head
    string printTail();                      // Printing the tail
    string printPos(int pos);                // Printing the called position
  
    int recCount(node* curr);                // Recursively counting the nodes in the linked list
    void recPrint(node* curr);               // Recursively printing the nodes in the linked list
    bool recSearch(node* curr, int target)   // Recursively searching the nodes in the linked list

    void recReversePrint(node* curr)         // Recursively and reversely printing the nodes in the linked list
};

3. Implement the functions:

Finally, we have to create all the functions that we declared in our class including, but not limited to: insertions, deletions, prints, and counts.

I. Insert at Head:

void insertHead(int d) {
  node *temp = new node;                     // Create a new node and allocate memory for it.

  temp->data = d;                            // Assign the data 'd' to the 'data' field of the new node.
  temp->next = nullptr;                      // Set the 'next' pointer of the new node to nullptr initially.

  if (head == nullptr) {
    head = temp;
    return;
  }

  temp->next = head;                         // Make the 'next' pointer of the new node point to the current head of the list.
  head = temp;                               // Update the 'head' pointer to make the new node the new head of the list.
}

II. Insert at End:

void insertTail(int d) {
  node *temp = new node;                     // Create a new node and allocate memory for it.

  temp->data = d;                            // Assign the data 'd' to the 'data' field of the new node.
  temp->next = nullptr;                      // Set the 'next' pointer of the new node to nullptr initially.

  if (head == nullptr) {                     // Check if the linked list is empty (head is nullptr), and if so, 
    head = temp;                             // make the new node the head and return, as it becomes the entire list.
    return;
  }

  node *curr = head;                         // Initialize a pointer 'curr' to traverse the list from the head.
  while (curr->next != nullptr) {            // Traverse the list until reaching the last node (where 'next' is nullptr).
    curr = curr->next;
  }
  curr->next = temp;                         // Make the 'next' pointer of the last node point to the new node.
}

III. Insert at Position:

void insertPos(int d, int p) {
  node *temp = new node;                     // Create a new node and allocate memory for it.
  temp->data = d;
  temp->next = nullptr;

  if (p == 0) {                              // Handle the case where 'p' is 0.
    if (head == nullptr) {                   // If the linked list is empty, make the new node the head.
      head = temp;
    } else {                                 // Otherwise, insert the new node at the beginning of the list.
      temp->next = head;
      head = temp;
    }
    return;
  }

  if (p >= recCount()) {                     // If 'p' is greater than or equal to the number of nodes in the list, do nothing.
    return;
  }

  node *curr = head;                         // Initialize pointers 'curr' and 'prev' to traverse the list.
  node *prev = nullptr;

  for (int i = 0; i < p; i++) {              // Traverse the list to find the position 'p' (0-based).
    if (curr == nullptr) {                   // If 'curr' becomes nullptr before reaching position 'p', do nothing.
      return;
    }
    prev = curr;
    curr = curr->next;
  }

  prev->next = temp;                         // Insert the new node between 'prev' and 'curr'.
  temp->next = curr;
}

IV. Delete at Head:

void removeHead() {
  if (head == nullptr) {                     // Check if the linked list is empty.
    return;                                  // If empty, there's nothing to remove.
  }
  node *temp = head;                         // Create a temporary pointer 'temp' to the current head node.
  head = head->next;                         // Update the 'head' pointer to point to the next node, removing the current head.
  delete temp;                               // Delete the old head node to free up memory.
}

V. Delete at End:

void removeTail() {
  if (head == nullptr) {                     // Check if the linked list is empty.
    return;                                  // If empty, there's nothing to remove.
  } else if (head->next == nullptr) {        // Special case: If there's only one node in the list, remove it.
    node *temp = head;
    head = head->next;
    delete temp;
  } else {
    node *curr = head;                       // Initialize pointers 'curr' and 'prev' to traverse the list.
    node *prev = nullptr;

    while (curr->next != nullptr) {          // Traverse the list to find the last node.
      prev = curr;
      curr = curr->next;
    }

    prev->next = nullptr;                    // Update 'prev' to point to nullptr, effectively removing the last node.
    delete curr;                             // Delete the old last node to free up memory.
  }
}

VI. Delete at Position:

void removePos(int p) {
  if (head == nullptr) {                     // Check if the linked list is empty.
    return;                                  // If empty, there's nothing to remove.
  } else if (p == 0) {                       // Special case: If 'p' is 0, remove the head node.
    node *temp = head;
    head = head->next;
    delete temp;
    return;
  }

  node *curr = head;                         // Initialize pointers 'curr' and 'prev' to traverse the list.
  node *prev = nullptr;

  for (int i = 0; i < p; i++) {              // Traverse the list to find the node at position 'p'.
    if (curr == nullptr) {                   // If 'curr' becomes nullptr before reaching position 'p', do nothing.
      return;
    }
    prev = curr;
    curr = curr->next;
    if (curr == nullptr) {                   // If 'curr' becomes nullptr during traversal, do nothing.
      return;
    }
  }

  prev->next = curr->next;                   // Update 'prev' to point to the node after 'curr', removing 'curr'.
  delete curr;                               // Delete the removed node to free up memory.
}

VII. Print at Head:

int printHead() {
  if (head == nullptr) {                     // Check if the linked list is empty.
    return -1;                               // If empty, return -1.
  }
  
  return head->data;                         // Return the data value of the head node.
}

VIII. Print at End:

int printTail() {
  if (head == nullptr) {                     // Check if the linked list is empty.
    return -1;                               // If empty, return -1.
  }
  
  node *curr = head;                         // Initialize a pointer 'curr' to traverse the list.

  while (curr->next != nullptr) {            // Traverse the list to find the last node.
    curr = curr->next;
  }

  return curr->data;                         // Return the data value of the last node.
}

IX. Print at Position:

int printPos(int p) {
  if (head == nullptr) {                     // Check if the linked list is empty.
    return -1;                               // If empty, return -1.
  } else if (head->next == nullptr) {        // Special case: If there's only one node in the list, return its data.
    return head->data;
  } else if (p >= recCount() || p < 0) {     // Check if 'p' is out of bounds.
    return -1;                               // If 'p' is out of bounds, return -1.
  }
  
  node *curr = head;                         // Initialize a pointer 'curr' to traverse the list.

  for (int i = 0; i < p; i++) {              // Traverse the list to find the node at position 'p'.
    if (curr == nullptr) {                   // If 'curr' becomes nullptr before reaching position 'p', return -1.
      return -1;
    }
    curr = curr->next;
  }

  return curr->data;                         // Return the data value of the node at position 'p'.
}

X. Recursive Traversal and Counting:

int recCount(node *curr) {
  if (curr == nullptr) {                     // Condition to stop if 'curr' is nullptr, since there are no more nodes to count.
    return 0;                                // Return 0 to indicate an empty list.
  }
  
  return recCount(curr->next) + 1;           // The change in parameter to update, what our function is specifically calling for
}
}

XI. Recursive Printing:

void recprint(node *curr) {
  if (curr == nullptr) {                     // Condition for when to stop traversing the linked list
    return;
  }
  cout << "data: " << curr->data << endl;    // The reason behind the need for repetition is to view everything within the list
  return recprint(curr->next);               // The change in parameter to update, what our function is specifically calling for
}

XI. Recursive Printing:

bool recSearch(node* curr, int t) {
    if (curr == nullptr) {                   // Condition to stop if the current node is nullptr, since the target is not found.
        return false;
    }

    if (curr->data == t) {                   // Check if the current node contains the target value.
        return true;
    }

    return recSearch(curr->next, t);         // Recursively search in the remaining part of the list.
}

XII. Reverse Recursive Printing:

void displayRevReccursive(node* curr) {
  if (curr == nullptr) {
    return;                                  // Condition to stop if the current node is nullptr
  }
  displayRevReccursive(curr->next);          // Recursively call on the next node
  cout << curr->value << " ";                // Print the value of the current node
}