What is Linked List and When do we need it?

Linked lists are a type of data structure that can be useful in various situations. Here are a few examples of when you might want to consider using a linked list:

  1. When you need to insert or delete elements from a list frequently: Linked lists allow you to insert and delete them from the list constantly, making them efficient for these operations.
  2. When you need to store a large number of items: Linked lists can be more memory efficient than other data structures, such as arrays, because they only store the data for each element and a pointer to the next element, rather than allocating space for all the details upfront.
  3. When you need to implement a stack or queue: Linked lists can be used to implement these data structures because they allow you to efficiently add and remove elements at the beginning or end of the list.
  4. When you need to store data that is constantly changing: Linked lists can be useful for storing data that is constantly changing, such as data from a stream because they can be easily modified as new data becomes available.

Of course, linked lists are not always the best choice, and you should consider the specific requirements of your application when deciding which data structure to use.

Example of Linked List:

class Node {
  public $data;
  public $next;

  public function __construct($data) {
    $this->data = $data;
    $this->next = NULL;
  }
}

class LinkedList {
  private $head;

  public function __construct() {
    $this->head = NULL;
  }

  public function add($data) {
    $node = new Node($data);

    if ($this->head == NULL) {
      $this->head = $node;
    } else {
      $current = $this->head;
      while ($current->next != NULL) {
        $current = $current->next;
      }
      $current->next = $node;
    }
  }

  public function delete($data) {
    if ($this->head == NULL) {
      return;
    }

    if ($this->head->data == $data) {
      $this->head = $this->head->next;
      return;
    }

    $current = $this->head;
    while ($current->next != NULL && $current->next->data != $data) {
      $current = $current->next;
    }

    if ($current->next != NULL) {
      $current->next = $current->next->next;
    }
  }

  public function printList() {
    $current = $this->head;
    while ($current != NULL) {
      echo $current->data . " ";
      $current = $current->next;
    }
    echo "\n";
  }
}

$list = new LinkedList();
$list->add(1);
$list->add(2);
$list->add(3);
$list->add(4);
$list->printList(); // prints 1 2 3 4
$list->delete(3);
$list->printList(); // prints 1 2 4
Linked List

This implementation includes a Node class that represents a single node in the linked list, with a data field and a next field that points to the next node in the list. The LinkedList class contains a head pointer that points to the first node in the list. The add method appends a new node to the end of the list, and the delete method removes a node with the given data from the list. The printList method prints the data of all the nodes in the list.