Linked List
Linked Lists

Linked Lists

Comments 0 Comment

Linked lists are a data structure in which the data nodes are linked together via pointers. Pointers point to something. In this case a node points to another node.

Linked lists are useful in building up other data structures like binary search trees etc. In this blog we’re not going to use pointers to memory as we would in a language like c, we’re rather going to emulate this with simple arrays.

We’re going to discuss then extremely briefly and then we’ll jump into code.

Singly Linked Lists

A singly linked list has a link only in one direction, so you can only traverse this list in one direction.

The data can be any type of data: numbers, strings, objects, etc. If we are traversing this list we know where to go to next because the “next” data points to it! Think about an array. Imagine we had an array where each item was an array with two items: data and next, where next is index of the next item in the array:

Array $linkedList = [
  [
     "data" => "This is data",
     "next" => 1,
  ],
  [
     "data" => "This is more data",
     "next" => 2,
  ],
  [
     "data" => "This is even more data",
     "next" => null,
  ]
];

In this example we can see that the next item points to the next index of the $linkedList item. This might seems silly and contrived. Granted, but these are first principles, just go with it for now. In real life your node objects will not be in an array, they will be objects created independently of one another with the only link between them being this next pointer.

Doubly Linked Lists

Double linked lists are similar except that they have bidirectional links:

Here there is a previous and a next item. To continue our Array metaphor:

Array $linkedList = [
  [
     "previous" => null,
     "data" => "This is data",
     "next" => 1,
  ],
  [
     "previous" => 0,
     "data" => "This is more data",
     "next" => 2,
  ],
  [
     "previous" => 1,
     "data" => "This is even more data",
     "next" => null,
  ]
];

Linked Lists are not Arrays

I want to stress again that linked lists are not arrays. I simply presented it as such above as a conceptual aid to thinking about how the previous / next pointers work. In real life Nodes will be objects (eg, $a = new Node(…);, $b = new Node(…); and they will contain pointers to one another.

Head / Tail

A linked list will have a head pointer which points to the first item in the linked list. It may also have a tail pointer which points to the last item in the list.

For instance, and even though I dislike my Array analogy, it may look like this in our fictitious array land:

$head = 0; // point to first item in list
$tail = 2; // points to last item in list
Array $linkedList = [
  [
     "previous" => null,
     "data" => "This is data",
     "next" => 1,
  ],
  [
     "previous" => 0,
     "data" => "This is more data",
     "next" => 2,
  ],
  [
     "previous" => 1,
     "data" => "This is even more data",
     "next" => null,
  ]
];

Linked List Operations

There are several operations we can carry out on linked lists, lets go through a few. We will only be considering double linked lists in these examples.

Insertion Operations

1. Insert a node at the beginning

There can be two conditions when inserting our new node at the beginning of the list:

  1. The list is completely empty
  2. The list is not empty.

If the list is empty our steps to insert the node are:

  1. Set the head pointer to the new node
  2. Set the previous pointer in the node to null to indicate that its the first item
  3. Set the next pointer in the node to null to indicate that its the last item
  4. Set the tail pointer to the new node

Let us now look at some real PHP code. We’ll stick to the PHP function name for prepending an item to an array, unshift:

class LinkedList
{
    private $head = null;
    private $tail = null;

    /**
     * Insert a new node at the beginning of the list
     */
    public function unshift(mixed $data)
    {
        $newNode = new Node($data);

        // 1. Set the head pointer to the new node
        $this->head = $newNode;

        // 2. Set the previous pointer in the node to null to indicate that its the first item
        $newNode->previous = null;


        // 3. Set the next pointer in the node to null to indicate that its the last item
        $newNode->next = null;


        // 4. Set the tail pointer to the new node
        $this->tail = $newNode;
        
        return $newNode;

    }
}

class Node
{

    public $previous   = null;
    public $next       = null;

    public function __construct(private mixed $data)
    {

    }

}

$linkedList = new LinkedList();

$node = $linkedList->unshift(data: "hello there");

print "\r\nLinked List:\r\n";
var_dump($linkedList);

print "\r\n-----------\r\n";
print "\r\nNode: \r\n";
var_dump($node);

-- output from var_dump --

Linked List:
object(LinkedList)#1 (2) {
  ["head":"LinkedList":private]=>
  object(Node)#2 (3) {
    ["previous"]=>
    NULL
    ["next"]=>
    NULL
    ["data":"Node":private]=>
    string(11) "hello there"
  }
  ["tail":"LinkedList":private]=>
  object(Node)#2 (3) {
    ["previous"]=>
    NULL
    ["next"]=>
    NULL
    ["data":"Node":private]=>
    string(11) "hello there"
  }
}

-----------

Node: 
object(Node)#2 (3) {
  ["previous"]=>
  NULL
  ["next"]=>
  NULL
  ["data":"Node":private]=>
  string(11) "hello there"
}

We can see from the var_dumps that the linked list correctly shows both the head and tail pointers pointing to this new node. It also shows that the node itself has the data we gave it as well as its previous and next pointers set to null.

There is a problem though. This code works only for an empty list when we’re inserting at the beginning of this empty list. If we call insert again it will insert the new node at the beginning but because we’re not handling the next pointer well it will set it to null, indicating that there are no more nodes, even though we called insert more than once.

We’ll fix this next.

If our list is not empty and we want to insert at the beginning of the list the steps are very similar, but we need to ensure that the rest of the list is not “lost” as it would be with our first try:

  1. Set the previous pointer of the node currently at head to our new node
  2. Set the next pointer of our new node to head
  3. Set the head pointer to the new node
  4. Set the previous pointer in the new node to null to indicate that its the first item.
class LinkedList
{
    private $head = null;
    private $tail = null;

    /**
     * Insert a new node at the beginning of the list
     */
    public function unshift(mixed $data)
    {
        $newNode = new Node($data);
    
        // check if this list has items already?
         if ($this->head != null) {
             // its not an empty list

             // 1. Set the previous pointer of the node currently at head to our new node
             $this->head->previous = $newNode;

             // 2. Set the next pointer of our new node to head
             $newNode->next = $this->head;
         }

         // 3. Set the head pointer to the new node
         $this->head = $newNode;

         // 4. Set the previous pointer in the new node to null to indicate that its the first item.
         $newNode->previous = null;

         if ($this->tail == null) {
             // This is the only item, point tail to it:
             $this->tail = $newNode;
         }
        
        return $newNode;

    }
}

class Node
{

    public $previous   = null;
    public $next       = null;

    public function __construct(public mixed $data)
    {

    }

}

$linkedList = new LinkedList();

$node = $linkedList->unshift(data: "hello there");

print "\r\nLinked List:\r\n";
var_dump($linkedList);

print "\r\n-----------\r\n";
print "\r\nNode: \r\n";
var_dump($node);


$node = $linkedList->unshift(data: "hi again");

print "\r\nLinked List:\r\n";
var_dump($linkedList);

print "\r\n-----------\r\n";
print "\r\nNode: \r\n";
var_dump($node);

-- output --

Linked List:
object(LinkedList)#1 (2) {
  ["head":"LinkedList":private]=>
  object(Node)#2 (3) {
    ["previous"]=>
    NULL
    ["next"]=>
    NULL
    ["data"]=>
    string(11) "hello there"
  }
  ["tail":"LinkedList":private]=>
  object(Node)#2 (3) {
    ["previous"]=>
    NULL
    ["next"]=>
    NULL
    ["data"]=>
    string(11) "hello there"
  }
}

-----------

Node: 
object(Node)#2 (3) {
  ["previous"]=>
  NULL
  ["next"]=>
  NULL
  ["data"]=>
  string(11) "hello there"
}

Linked List:
object(LinkedList)#1 (2) {
  ["head":"LinkedList":private]=>
  object(Node)#3 (3) {
    ["previous"]=>
    NULL
    ["next"]=>
    object(Node)#2 (3) {
      ["previous"]=>
      *RECURSION*
      ["next"]=>
      NULL
      ["data"]=>
      string(11) "hello there"
    }
    ["data"]=>
    string(8) "hi again"
  }
  ["tail":"LinkedList":private]=>
  object(Node)#2 (3) {
    ["previous"]=>
    object(Node)#3 (3) {
      ["previous"]=>
      NULL
      ["next"]=>
      *RECURSION*
      ["data"]=>
      string(8) "hi again"
    }
    ["next"]=>
    NULL
    ["data"]=>
    string(11) "hello there"
  }
}

-----------

Node: 
object(Node)#3 (3) {
  ["previous"]=>
  NULL
  ["next"]=>
  object(Node)#2 (3) {
    ["previous"]=>
    *RECURSION*
    ["next"]=>
    NULL
    ["data"]=>
    string(11) "hello there"
  }
  ["data"]=>
  string(8) "hi again"
}

With this adjusted code we can now insert a new node at the beginning of the list whether the list is empty or not. If you trace through the debug output you’ll see that the pointers point correctly (even though the new node appears second in the var_dump the head pointer points to it, and tail to the first item we created, and the next/previous pointers point in the right directions, so this list is working well.

2. Inserting a new node at the end of the list

Lets map out the steps needed to append a new node to the end of the list. We’ll stick with the PHP function name for appending to an array, push:

  1. Set the previous pointer of the new node to tail
  2. Set the next pointer of our tail node to the new node
  3. Set the tail pointer to the new node
  4. Set the next pointer of the new node to null
class LinkedList
{
    public $head = null;
    public $tail = null;

    /**
     * Insert a new node at the end of the list
     */
    public function push(mixed $data)
    {
        $newNode = new Node($data);


        if ($this->tail) {
            // The list is not empty

            // 1. Set the previous pointer of the new node to tail
            $newNode->previous = $this->tail;

            // 2. Set the next pointer of our tail node to the new node
            $this->tail->next = $newNode;
        }

        // 3. Set the tail pointer to the new node
        $this->tail = $newNode;


        // 4. Set the next pointer of the new node to null
        $newNode->next = null;

        if ($this->head == null) {
            // This is the only item, point head to it:
            $this->head = $newNode;
        }

        return $newNode;

    }
}

class Node
{

    public $previous   = null;
    public $next       = null;

    public function __construct(public mixed $data)
    {

    }

}

$linkedList = new LinkedList();

$node = $linkedList->push(data: "Data added first");

print "\r\nLinked List:\r\n";
print_r($linkedList);

print "\r\n-----------\r\n";
print "\r\nNode: \r\n";
print_r($node);

print "\r\n===========\r\n";

$node = $linkedList->push(data: "data added second");

print "\r\nLinked List:\r\n";
print_r($linkedList);

print "\r\n-----------\r\n";
print "\r\nNode: \r\n";
print_r($node);

-- output -- 

Linked List:
LinkedList Object
(
    [head] => Node Object
        (
            [previous] => 
            [next] => 
            [data] => Data added first
        )

    [tail] => Node Object
        (
            [previous] => 
            [next] => 
            [data] => Data added first
        )

)

-----------

Node: 
Node Object
(
    [previous] => 
    [next] => 
    [data] => Data added first
)

===========

Linked List:
LinkedList Object
(
    [head] => Node Object
        (
            [previous] => 
            [next] => Node Object
                (
                    [previous] => Node Object
 *RECURSION*
                    [next] => 
                    [data] => data added second
                )

            [data] => Data added first
        )

    [tail] => Node Object
        (
            [previous] => Node Object
                (
                    [previous] => 
                    [next] => Node Object
 *RECURSION*
                    [data] => Data added first
                )

            [next] => 
            [data] => data added second
        )

)

3. Inserting at some point in the list

We’ve successfully added a method to push nodes to the end of the list. Now we need a method for adding items “into” the list after some given node. As before, lets list the steps here before we write the code. We’ll call the method insertAfter:

There important nodes are givenNode, nextNode (which is the node pointed to by givenNode’s next pointer) and newNode which is the new node we’re adding.

  1. Set newNode’s next pointer to givenNode’s next pointer
  2. Set newNode’s previous pointer to givenNode
  3. Set nextNode’s previous pointer to newNode
  4. Set givenNode’s next pointer to newNode

And the code for this looks like this:

class LinkedList
{
    public $head = null;
    public $tail = null;

    /**
     * Insert a new node after given node
     */
    public function insertAfter(mixed $data, Node $givenNode): Node
    {
        $newNode = new Node($data);


        // 1. Set newNode's next pointer to givenNode's next pointer
        $newNode->next = $givenNode->next;

        // if we've inserted it at the end of the list
        // set tail to newNode
        if ($newNode->next == null) {
            $this->tail = $newNode;
        }

        // 2. Set newNode's previous pointer to givenNode
        $newNode->previous = $givenNode;

        // 3. Set nextNode's previous pointer to newNode
        // Check if givenNode's next is set.
        // if its null we're at the end of the list
        if ($givenNode->next) {
            $givenNode->next->previous = $newNode;
            // the above line may seem a little weird.
            // We could rewrite it like this to be clearer:
            // $nextNode = $givenNode->next;
            // $nextNode->previous = $newNode;

        }
        // 3. Set givenNode's next pointer to newNode
        $givenNode->next = $newNode;


        return $newNode;

    }
}

class Node
{

    public $previous   = null;
    public $next       = null;

    public function __construct(public mixed $data)
    {

    }

}

$linkedList = new LinkedList();

// just a cheat to add our first node into the linked list here
// for our tests..

$firstNode = new Node("one");
$linkedList->head = $firstNode;
$linkedList->tail = $firstNode;


$threeNode = $linkedList->insertAfter(data: "three", givenNode: $firstNode);

$twoNode = $linkedList->insertAfter(data: "two", givenNode: $firstNode);

$fourNode = $linkedList->insertAfter(data: "four", givenNode: $threeNode);


$currentNode = $linkedList->head;
while ($currentNode != null) {
    print $currentNode->data."\r\n";
    $currentNode = $currentNode->next;
}
print "done";

-- output --

one
two
three
four

We can see that the output is as we expected even though we added the items in a not sequential order.

All of our inserts are working as expected. We can now combine our three insert methods, unshift, insertAfter and next into the linkedList class (5_all_insert_methods.php).

Delete Operations

What we can insert into a list we can remove. We’ll move quite quickly through our examples now with the steps, the code and little to no explanation. We’re also not going to code each type individually, we’ll give the steps below individually and then code it up once.

1. Delete from the beginning of the list (method shift)

  1. Set head to the node pointed to by head’s next pointer
  2. Set the previous pointer of the node pointed to by head’s next pointer to null.

2. Delete from the end of the list (method pop)

  1. Set tail to the node pointed to by tail’s previous pointer
  2. Set the next pointer of the node pointed to by tail’s previous pointer to null.

3. Delete a value from the list (method delete)

  1. Create a Node variable called CurrentNode and set it to head
  2. If CurrentNode->data does not match our search string set CurrentData to CurrentData->next
  3. If CurrentNode->data does match our search string then
  4. Set next pointer of node pointed to by CurrentNode’s previous pointer to CurrentNode’s next pointer.
  5. Set previous pointer of the node pointed to by CurrentNode’s next pointer to CurrrentNode’s previous pointer.

Reversing

The last method I’ll look at in this post is reversing the order of the list. I realise that we could implement a traverse method, but we’ve already kind of done that in the debug outputs and in the delete() method. We could also implement a find() method but again, we’ve already sort of done this in the delete() method, so I’ll leave that as an exercise for you.

Reversing is extremely simple:

  1. Loop through each node, starting at head
  2. When we reach the last node:
    • set tail = head
    • set head = last node
  3. For each node, swop the previous and next pointers
    public function reverse()
    {

        // 1. Loop through each node, starting at head
        $currentNode = $this->head;
        $pointer = $currentNode;
        while ($pointer != null) {

            $pointer = $currentNode->next;

            if ($currentNode->next == null) {

                // 2. When we reach the last node
                //    set tail = head
                //    set head = last node

                $this->tail = $this->head;
                $this->head = $currentNode;

            }

            // 3. For each node, swop the previous and next pointers
            $previous = $currentNode->previous;
            $currentNode->previous = $currentNode->next;
            $currentNode->next = $previous;

            $currentNode = $pointer;

        }
    
    }

-- output --

one
two
three
four
five

-----------------------
five
four
three
two
one

GitHub Code

You can download the code for this blog post at https://github.com/jsmcm/blogs.php.linked-lists

Share

Leave a Reply

Your email address will not be published. Required fields are marked *