Linked list

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

<?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;
}
​
// 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);
}
}

• 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)