当前位置:网站首页>Linked list

Linked list

2020-11-08 23:46:27 Spicy chicken

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)

版权声明
本文为[Spicy chicken]所创,转载请带上原文链接,感谢