Linked list

brief introduction

Array ： In the case of index semantics , Using the index to get values , A quick query .
- The ability to access randomly
Linked list ： It's not suitable for semantic indexing
- Real dynamics , There's no need to deal with fixed capacity

structure

Build node classes

<?php
declare(strict_types=1);

class Node
{
// The element value of this node
public $e;
// Pointer to the next node
public $next;

public function __construct($e = null, $next = null)
{
$this->e = $e;
$this->next = $next;
}

// Output the element value of the node object as a string
public function __toString(): string
{
return (string)$this->e;
}
}

Build a linked list implementation class

Define properties and constructors

<?php
declare(strict_types=1);

require_once 'Node.php';

class LinkedList
{
// Chain header pointer
private $head;

// The number of elements in the linked list
private int $size;

public function __construct()
{
$this->head = null;
$this->size = 0;
}
}

Get the number of effective elements in the linked list

// Get the number of effective elements in the linked list
public function getSize(): int
{
return $this->size;
}

Judge whether the list is empty

// Is the list empty
public function isEmpty(): bool
{
return $this->size === 0;
}

Insert an element in the chain header

// Insert an element in the chain header
public function addFrist($e): void
{
// $nodeObj = new Node($e);
// $nodeObj->next = $this->head;
// $this->head = $nodeObj;
$this->head = new Node($e, $this->head);
$this->size++;
}

In the index Bit insertion element $e

// Go to index Bit to add a new element e
// To assist in understanding and practicing , Suppose the linked list is also indexed
public function add(int $index, $e): void
{
if ($index < 0 || $index > $this->size) {
throw new RuntimeException('index Wrong value ');
}
if ($index === 0) {
$this->addFrist($e);
} else {
$prev = $this->head;
for ($i = 0; $i < $index - 1; $i++) {
$prev = $prev->next;
}
$prev->next = new Node($e, $prev->next);
$this->size++;
}
}

Insert the element at the end of the list $e

// Insert the element at the end of the filing table $e
public function addLast($e): void
{
$this->add($this->size, $e);
}

Introduce virtual head node , The logic is the same no matter which node is inserted into the linked list

Set the first index The value of bit is e

// Set the first index Bit element value
// To assist in understanding and practicing , Suppose the linked list also has an index
public function set(int $index, $e): void
{
if ($index < 0 || $index >= $this->size) {
throw new RuntimeException('index Wrong value ');
}
// Use the next element of the virtual head node as the starting bit
$cur = $this->dummyHead->next;
for ($i = 0; $i < $index; $i++) {
$cur = $cur->next;
}
$cur->e = $e;
}

Find out if the element exists

// Find out if there are elements in the list $e
public function contains($e): bool
{
// Use the next element of the virtual head node as the starting bit
$cur = $this->dummyHead->next;
while ($cur !== null) {
if ($cur->e === $e) {
return true;
}
$cur = $cur->next;
}
return false;
}

Remove elements

// Delete the first index Bit element value , And return the deleted element value
// To assist in understanding and practicing , Suppose the linked list also has an index
public function remove(int $index)
{
if ($index < 0 || $index >= $this->size) {
throw new RuntimeException('index Wrong value ');
}
$prev = $this->dummyHead;
for ($i = 0; $i < $index; $i++) {
$prev = $prev->next;
}
$retNode = $prev->next;
$prev->next = $retNode->next;
$retNode->next = null;
$this->size--;

return $retNode->e;
}

// Delete first element
public function removeFrist()
{
return $this->remove(0);
}

// Delete the last element
public function removeLast()
{
return $this->remove($this->size - 1);
}

Object to string magic method

public function __toString(): string
{
$string = '';
$cur = $this->dummyHead->next;
while ($cur !== null) {
$string .= ($cur . '->');
$cur = $cur->next;
}
$string .= 'NULL
';
return $string;
}

Complete code

<?php
declare(strict_types=1);

require_once 'Node.php';

class LinkedList
{
// Chain header pointer
// private $head;

// Virtual head node
private $dummyHead;

// The number of elements in the linked list
private int $size;

public function __construct()
{
// $this->head = null;
$this->dummyHead = new Node(null, null);
$this->size = 0;
}

// Get the number of effective elements in the linked list
public function getSize(): int
{
return $this->size;
}

// Is the list empty
public function isEmpty(): bool
{
return $this->size === 0;
}

// Insert an element in the chain header
// public function addFrist($e): void
// {
// // $nodeObj = new Node($e);
// // $nodeObj->next = $this->head;
// // $this->head = $nodeObj;
// $this->head = new Node($e, $this->head);
// $this->size++;
// }

// Go to index Bit to add a new element e
// To assist in understanding and practicing , Suppose the linked list also has an index
// public function add(int $index, $e): void
// {
// if ($index < 0 || $index > $this->size) {
// throw new RuntimeException('index Wrong value ');
// }
// if ($index === 0) {
// $this->addFrist($e);
// } else {
// $prev = $this->head;
// for ($i = 0; $i < $index - 1; $i++) {
// $prev = $prev->next;
// }
// $prev->next = new Node($e, $prev->next);
// $this->size++;
// }
// }

// Go to index Bit to add a new element e
public function add(int $index, $e): void
{
if ($index < 0 || $index > $this->size) {
throw new RuntimeException('index Wrong value ');
}

$prev = $this->dummyHead;
for ($i = 0; $i < $index; $i++) {
$prev = $prev->next;
}

$prev->next = new Node($e, $prev->next);

$this->size++;
}

// Insert the element at the end of the filing table $e
public function addLast($e): void
{
$this->add($this->size, $e);
}

// Insert an element in the chain header
public function addFrist($e): void
{
$this->add(0, $e);
}

// For the first index Bit element value
// To assist in understanding and practicing , Suppose the linked list also has an index
public function get(int $index)
{
if ($index < 0 || $index >= $this->size) {
throw new RuntimeException('index Wrong value ');
}

// Use the next element of the virtual head node as the starting bit
$cur = $this->dummyHead->next;

for ($i = 0; $i < $index; $i++) {
$cur = $cur->next;
}
return $cur->e;
}

// Get the first element of the linked list
public function getFrist()
{
return $this->get(0);
}

// Get the last element of the list
public function getLast()
{
return $this->get($this->size - 1);
}

// Set the first index Bit element value
// To assist in understanding and practicing , Suppose the linked list also has an index
public function set(int $index, $e): void
{
if ($index < 0 || $index >= $this->size) {
throw new RuntimeException('index Wrong value ');
}
// Use the next element of the virtual head node as the starting bit
$cur = $this->dummyHead->next;
for ($i = 0; $i < $index; $i++) {
$cur = $cur->next;
}
$cur->e = $e;
}

// Find out if there are elements in the list $e
public function contains($e): bool
{
// Use the next element of the virtual head node as the starting bit
$cur = $this->dummyHead->next;

while ($cur !== null) {
if ($cur->e === $e) {
return true;
}
$cur = $cur->next;
}
return false;
}

// Delete the first index Bit element value , And return the deleted element value
// To assist in understanding and practicing , Suppose the linked list also has an index
public function remove(int $index)
{
if ($index < 0 || $index >= $this->size) {
throw new RuntimeException('index Wrong value ');
}
$prev = $this->dummyHead;
for ($i = 0; $i < $index; $i++) {
$prev = $prev->next;
}
$retNode = $prev->next;
$prev->next = $retNode->next;
$retNode->next = null;
$this->size--;

return $retNode->e;
}

// Delete first element
public function removeFrist()
{
return $this->remove(0);
}

// Delete the last element
public function removeLast()
{
return $this->remove($this->size - 1);
}

public function __toString(): string
{
$string = '';
$cur = $this->dummyHead->next;
while ($cur !== null) {
$string .= ($cur . '->');
$cur = $cur->next;
}
$string .= 'NULL
';
return $string;
}
}

test

require DIR . '/LinkedList/LinkedList.php';
$linkedListObj = new LinkedList();
for ($i = 0; $i < 5; $i++) {
$linkedListObj->addFrist($i);
echo $linkedListObj;
}
$linkedListObj->add(2,'abc');
echo $linkedListObj;

$linkedListObj->removeLast();
echo $linkedListObj;
$linkedListObj->removeFrist();
echo $linkedListObj;
$linkedListObj->remove(2);
echo $linkedListObj;

Time complexity

Add operation
- addLast() by O(n)
- addFirst() by O(1)
- add() by O(n/2)~O(n)
Delete operation
- removeLast() by O(n)
- removeFirst() by O(1)
- remove() by O(n/2)~O(n)
Modify the operating
- set() by O(n)
Search operation
- get() by O(n)
- contains() by O(n)
increase ：O(n)
Delete ：O(n)
Change ： Unknown index O(n)
check ： Unknown index O(n)
If you just add, delete, modify and query the chain header, they are all O(1)