A linked list is a linear data structure, which contains node structure and each node contains two elements. A data part that stores the value at that node and next part that stores the link to the next node as shown in the below image:

The first node also known as HEAD is usually used to traverse through the linked list. The last node (next part of the last node) points to NULL. The list can be visualized as a chain of nodes, where every node points to the next node.

## Implementation of Singly Linked List

## Representation:

In PHP, singly linked list can be represented as a class and a Node as a separate class. The LinkedList class contains a reference of Node class type.

```
//node structure
class Node {
public $data;
public $next;
}
class LinkedList {
public $head;
//constructor to create an empty LinkedList
public function __construct(){
$this->head = null;
}
};
```

## Create a Linked List

Let us create a simple linked list which contains three data nodes.

<?php
//node structure
class Node {
public $data;
public $next;
}
class LinkedList {
public $head;
//constructor to create an empty LinkedList
public function __construct(){
$this->head = null;
}
};
// test the code
//create an empty LinkedList
$MyList = new LinkedList();
//Add first node.
$first = new Node();
$first->data = 10;
$first->next = null;
//linking with head node
$MyList->head = $first;
//Add second node.
$second = new Node();
$second->data = 20;
$second->next = null;
//linking with first node
$first->next = $second;
//Add third node.
$third = new Node();
$third->data = 30;
$third->next = null;
//linking with second node
$second->next = $third;
?>

## Traverse a Linked List

Traversing through a linked list is very easy. It requires creating a temp node pointing to the head of the list. If the temp node is not null, display its content and move to the next node using temp next. Repeat the process till the temp node becomes null. If the temp node is empty at the start, then the list contains no item.

The function *PrintList* is created for this purpose. It is a **3-step process**.

```
public function PrintList() {
//1. create a temp node pointing to head
$temp = new Node();
$temp = $this->head;
//2. if the temp node is not null continue
// displaying the content and move to the
// next node till the temp becomes null
if($temp != null) {
echo "\nThe list contains: ";
while($temp != null) {
echo $temp->data." ";
$temp = $temp->next;
}
} else {
//3. If the temp node is null at the start,
// the list is empty
echo "\nThe list is empty.";
}
}
```

## Add a new node at the end of the Linked List

In this method, a new node is inserted at the end of the linked list. For example — if the given List is 10->20->30 and a new element 100 is added at the end, the Linked List becomes 10->20->30->100.

Inserting a new node at the end of the Linked List is very easy. First, a new node with given element is created. It is then added at the end of the list by linking the last node to the new node.

The function *push_back* is created for this purpose. It is a **6-step process**.

```
public function push_back($newElement) {
//1. allocate node
$newNode = new Node();
//2. assign data element
$newNode->data = $newElement;
//3. assign null to the next of new node
$newNode->next = null;
//4. Check the Linked List is empty or not,
// if empty make the new node as head
if($this->head == null) {
$this->head = $newNode;
} else {
//5. Else, traverse to the last node
$temp = new Node();
$temp = $this->head;
while($temp->next != null) {
$temp = $temp->next;
}
//6. Change the next of last node to new node
$temp->next = $newNode;
}
}
```

The below is a complete program that uses above discussed all concepts of the linked list.

```
<?php
//node structure
class Node {
public $data;
public $next;
}
class LinkedList {
public $head;
public function __construct(){
$this->head = null;
}
//Add new element at the end of the list
public function push_back($newElement) {
$newNode = new Node();
$newNode->data = $newElement;
$newNode->next = null;
if($this->head == null) {
$this->head = $newNode;
} else {
$temp = new Node();
$temp = $this->head;
while($temp->next != null) {
$temp = $temp->next;
}
$temp->next = $newNode;
}
}
//display the content of the list
public function PrintList() {
$temp = new Node();
$temp = $this->head;
if($temp != null) {
echo "\nThe list contains: ";
while($temp != null) {
echo $temp->data." ";
$temp = $temp->next;
}
} else {
echo "\nThe list is empty.";
}
}
};
// test the code
$MyList = new LinkedList();
//Add three elements at the end of the list.
$MyList->push_back(10);
$MyList->push_back(20);
$MyList->push_back(30);
$MyList->PrintList();
?>
```

The output of the above code will be:

```
The list contains: 10 20 30
```

Do linked lists have any application in competitive programming?

I think the only thing I'd use them for is a queue, and in that case an array-based implementation (e.g. Java

`ArrayDeque`

) is more performant.I'm curious if anyone knows any problems that benefit from a linked list, or draws inspiration from the ideas underlying a linked list.

I have read the "Competitive Programming 3" and authors point to one such problem where linked list is indeed helpful. (They also said that this is the only problem of this kind that they found)

https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3139

Thank you, I will check it out!

This can be solved using deque

is a deque always better than a queue? i only ever use queue for BFS but that's about it

For anyone else curious, I used the ideas behind LL when solving 1282E - The Cake Is a Lie.

SpoilerWhen reconstructing the polygon, I built up the polygon by representing the vertices as a circular linked list (starting with just 2 vertices), taking the pieces in reverse order, and "inserting" a vertex in the appropriate spot in the circular LL.

89609520