type Node[T any] struct {
    Value T
    Next  *Node[T]
}

type LinkedList[T any] struct {
    Head *Node[T]
    Size int
}

func (l *LinkedList[T]) PushFront(val T) {
    node := &Node[T]{Value: val, Next: l.Head}
    l.Head = node
    l.Size++
}

func (l *LinkedList[T]) PopFront() (T, bool) {
    if l.Head == nil {
        var zero T
        return zero, false
    }
    val := l.Head.Value
    l.Head = l.Head.Next
    l.Size--
    return val, true
}

<?php
declare(strict_types=1);

$list = new \SplDoublyLinkedList();
$list->push('a');    // в хвост
$list->push('b');
$list->push('c');
$list->unshift('0'); // в голову

foreach ($list as $value) {
    echo $value . "\n"; // 0, a, b, c
}

// O(1) операции на концах
$first = $list->shift(); // удаляем '0' из головы
$last = $list->pop();    // удаляем 'c' из хвоста

echo count($list); // 2

// Доступ по индексу O(n) - честный linked list
$middle = $list[0];

В PHP писать связный список руками не нужно - есть \SplDoublyLinkedList (база для \SplStack и \SplQueue). Он реализует Iterator, Countable, ArrayAccess, поддерживает обход в обе стороны.

import "container/list"

func main() {
    l := list.New()

    // Вставка
    l.PushBack("first")
    l.PushBack("second")
    l.PushFront("zero")

    // Итерация
    for e := l.Front(); e != nil; e = e.Next() {
        fmt.Println(e.Value) // zero, first, second
    }

    // Удаление
    l.Remove(l.Front())
}

<?php
declare(strict_types=1);

$list = new \SplDoublyLinkedList();
$list->push('first');
$list->push('second');
$list->unshift('zero');

// Итерация (порядок такой же: zero, first, second)
foreach ($list as $value) {
    echo $value . "\n";
}

// Удаление головы
$list->shift();
// Или offsetUnset по индексу:
$list->offsetUnset(0);

type LRUCache struct {
    capacity int
    items    map[string]*list.Element
    order    *list.List
}

type entry struct {
    key   string
    value string
}

func NewLRUCache(capacity int) *LRUCache {
    return &LRUCache{
        capacity: capacity,
        items:    make(map[string]*list.Element),
        order:    list.New(),
    }
}

func (c *LRUCache) Get(key string) (string, bool) {
    if elem, ok := c.items[key]; ok {
        c.order.MoveToFront(elem)
        return elem.Value.(*entry).value, true
    }
    return "", false
}

func (c *LRUCache) Put(key, value string) {
    if elem, ok := c.items[key]; ok {
        c.order.MoveToFront(elem)
        elem.Value.(*entry).value = value
        return
    }

    if c.order.Len() >= c.capacity {
        oldest := c.order.Back()
        c.order.Remove(oldest)
        delete(c.items, oldest.Value.(*entry).key)
    }

    elem := c.order.PushFront(&entry{key, value})
    c.items[key] = elem
}

<?php
declare(strict_types=1);

final class LRUCache
{
    /** @var \SplDoublyLinkedList */
    private \SplDoublyLinkedList $order;

    /** @var array<string, \SplDoublyLinkedList> Map key → node (упрощено: храним key→list-ref) */
    private array $items = [];

    public function __construct(private readonly int $capacity) {
        $this->order = new \SplDoublyLinkedList();
    }

    public function get(string $key): ?string
    {
        if (!isset($this->items[$key])) {
            return null;
        }

        $value = $this->items[$key];
        $this->touch($key, $value);
        return $value;
    }

    public function put(string $key, string $value): void
    {
        if (isset($this->items[$key])) {
            $this->touch($key, $value);
            return;
        }

        if (count($this->items) >= $this->capacity) {
            $oldest = $this->order->shift();
            unset($this->items[$oldest]);
        }

        $this->order->push($key);
        $this->items[$key] = $value;
    }

    private function touch(string $key, string $value): void
    {
        // Удаляем старую позицию ключа и кладём в хвост (most recently used)
        foreach ($this->order as $idx => $k) {
            if ($k === $key) {
                $this->order->offsetUnset($idx);
                break;
            }
        }
        $this->order->push($key);
        $this->items[$key] = $value;
    }
}

// Прагматичный вариант для прода - Symfony Cache:
// use Symfony\Component\Cache\Adapter\ArrayAdapter;
// $cache = new ArrayAdapter(defaultLifetime: 0, storeSerialized: false, maxLifetime: 0, maxItems: 100);
// $cache->get('user:42', fn () => $repo->find(42));

В PHP LRU удобно собирать на \SplDoublyLinkedList + массив-индекс. Но если задача прикладная (HTTP-кеш, мемоизация репозитория) - бери готовое: Symfony\Component\Cache\Adapter\ArrayAdapter или LRUCacheTrait из wikimedia/at-ease-стиля библиотек.