Link list in php

Implementation of Linked List in PHP

A linked list is a linear data structure, which contains node structure and each node contains two elements. A data part that stores the value at that node and next part that stores the link to the next node as shown in the below image:

The first node also known as HEAD is usually used to traverse through the linked list. The last node (next part of the last node) points to NULL. The list can be visualized as a chain of nodes, where every node points to the next node.

Implementation of Singly Linked List

Representation:

In PHP, singly linked list can be represented as a class and a Node as a separate class. The LinkedList class contains a reference of Node class type.

//node structure class Node < public $data; public $next; >class LinkedList < public $head; //constructor to create an empty LinkedList public function __construct()< $this->head = null; > >; 

Create a Linked List

Let us create a simple linked list which contains three data nodes.

  class LinkedList < public $head; //constructor to create an empty LinkedList public function __construct()< $this->head = null; > >; // test the code //create an empty LinkedList $MyList = new LinkedList(); //Add first node. $first = new Node(); $first->data = 10; $first->next = null; //linking with head node $MyList->head = $first; //Add second node. $second = new Node(); $second->data = 20; $second->next = null; //linking with first node $first->next = $second; //Add third node. $third = new Node(); $third->data = 30; $third->next = null; //linking with second node $second->next = $third; ?> 

Traverse a Linked List

Traversing through a linked list is very easy. It requires creating a temp node pointing to the head of the list. If the temp node is not null, display its content and move to the next node using temp next. Repeat the process till the temp node becomes null. If the temp node is empty at the start, then the list contains no item.

The function PrintList is created for this purpose. It is a 3-step process.

 public function PrintList() < //1. create a temp node pointing to head $temp = new Node(); $temp = $this->head; //2. if the temp node is not null continue // displaying the content and move to the // next node till the temp becomes null if($temp != null) < echo "\nThe list contains: "; while($temp != null) < echo $temp->data." "; $temp = $temp->next; > > else < //3. If the temp node is null at the start, // the list is empty echo "\nThe list is empty."; >> 

Add a new node at the end of the Linked List

In this method, a new node is inserted at the end of the linked list. For example — if the given List is 10->20->30 and a new element 100 is added at the end, the Linked List becomes 10->20->30->100.

Inserting a new node at the end of the Linked List is very easy. First, a new node with given element is created. It is then added at the end of the list by linking the last node to the new node.

The function push_back is created for this purpose. It is a 6-step process.

public function push_back($newElement) < //1. allocate node $newNode = new Node(); //2. assign data element $newNode->data = $newElement; //3. assign null to the next of new node $newNode->next = null; //4. Check the Linked List is empty or not, // if empty make the new node as head if($this->head == null) < $this->head = $newNode; > else < //5. Else, traverse to the last node $temp = new Node(); $temp = $this->head; while($temp->next != null) < $temp = $temp->next; > //6. Change the next of last node to new node $temp->next = $newNode; > > 

The below is a complete program that uses above discussed all concepts of the linked list.

  class LinkedList < public $head; public function __construct()< $this->head = null; > //Add new element at the end of the list public function push_back($newElement) < $newNode = new Node(); $newNode->data = $newElement; $newNode->next = null; if($this->head == null) < $this->head = $newNode; > else < $temp = new Node(); $temp = $this->head; while($temp->next != null) < $temp = $temp->next; > $temp->next = $newNode; > > //display the content of the list public function PrintList() < $temp = new Node(); $temp = $this->head; if($temp != null) < echo "\nThe list contains: "; while($temp != null) < echo $temp->data." "; $temp = $temp->next; > > else < echo "\nThe list is empty."; >> >; // test the code $MyList = new LinkedList(); //Add three elements at the end of the list. $MyList->push_back(10); $MyList->push_back(20); $MyList->push_back(30); $MyList->PrintList(); ?> 

The output of the above code will be:

The list contains: 10 20 30 

Источник

Implementing a linked list in PHP with full code example

In this article, you will learn how to implement a singly linked list in PHP:

Let’s start by learning the basic concepts and terminology used in linked lists.

Linked list terminology and illustration

Before we dive into the implementation, it is important to understand some of the key terms and concepts used in linked lists:

Node — A node is the basic building block of a linked list. It is an object that stores a data element and a reference to the next node in the list. In a singly linked list, each node only has a single reference, pointing to the next node in the sequence.

Head — The head of a linked list is the first node in the sequence. It is the node that is accessed first when traversing the list.

Tail — The tail of a linked list is the last node in the sequence. It is the node that the last node in the list points to.

Link — A link is a reference that a node has to the next node in the sequence. In a singly linked list, each node has a single link pointing to the next node in the list.

Length — The length of a linked list is the number of nodes in the list.

Here’s an illustration of a linked list data structure:

Now that you know the basic concepts and terminology, let’s move on to the implementation of a singly linked list in PHP.

Implementing a singly linked list in PHP

First, you need to define a Node class that represents a single node in the linked list.

This class will have two properties: $data which will store the data element of the node, and $next which will store a reference to the next node in the sequence.

   Next, define a SinglyLinkedList class that represents the linked list itself.

This class will have a $head property that stores a reference to the first node in the list, and a $tail property that stores a reference to the last node in the list.

   Now that we have defined the basic structure of our linked list, let’s move on to implementing some common operations on a linked list.

Inserting a node at the beginning of the list

The first operation that we will implement is inserting a node at the beginning of the list. This operation is commonly known as “pushing” a node onto the list.

1. Create a new Node object with the given data element.
2. Set the next property of the new node to the current head of the list.
3. Set the head of the list to the new node.

Here is the implementation of this operation in the SinglyLinkedList class:

The next operation that we will implement is inserting a node at the end of the list. This operation is commonly known as “appending” a node to the list.

1. Create a new Node object with the given data element.
2. Set the next property of the current tail of the list to the new node.
3. Set the tail of the list to the new node.

Below is the implementation of this operation in the SinglyLinkedList class:

The next operation that we will implement is removing a node from the beginning of the list.

This operation is commonly known as “popping” a node from the list.

1. Check if the list is empty. If it is, return null .
2. Set the head of the list to the node next to head.
3. Return the removed node.

The code below shows the implementation of this operation in the SinglyLinkedList class:

The next operation that we will implement is removing a node from the end of the list. This operation is commonly known as “unshifting” a node from the list.

1. Check if the list is empty. If it is, return null .
2. If the list has only one node, set the head and tail of the list to null .
3. Traverse the list to find the node before the last node.
4. Set the next property of the node before the last node to null .
5. Set the tail of the list to the node before the last node.
6. Return the removed node.

Here is the implementation of this operation in the SinglyLinkedList class:

1. Initialize a length variable to 0.
2. Traverse the list and increment the length variable by 1 for each node.
3. Return the length variable.

Here is the implementation of this operation in the SinglyLinkedList class:

1. Initialize a $current variable to the head of the list
2. Loop through the list until we reach the end of the list. At each iteration of the loop, do the following:
   1. Print the data property of the current node.
   2. Set the current variable to the next node.

   Here is the implementation of traverse() in the SinglyLinkedList class:

   1. Initialize a $current variable to the head of the list.
   2. Loop through the list until we reach the end of the list. At each iteration of the loop, do the following:
      1. If the data property of the current node matches the search query, return that node.
      2. Set the $current variable to the next node.

      Here is the implementation of search() in the SinglyLinkedList class:

      The final operation that we will implement is removing a node from the middle of the list. This operation is commonly known as “splicing” a node from the list.

      1. Search the list for the node with the given data value. If the node is not found, return null .
      2. If the node to be removed is the head of the list, set the head of the list to the next node.
      3. If the node to be removed is the tail of the list, set the tail of the list to the previous node.
      4. if the node to be removed is neither the head nor the tail , set the next property of the previous node to the next of the current node.
      5. Return the removed node.

      Here is the implementation of this splice() in the SinglyLinkedList class:

            With that, you have successfully implemented a singly linked list in PHP!

      The complete SinglyLinkedList class code

      Here is the complete SinglyLinkedList class with all of the implemented operations:

                                         "             Let’s write some code to test the implementation as shown below:

      Conclusion

      A linked list is a data structure that consists of a sequence of nodes, where each node contains a data element and a reference to the next node in the sequence.

      Linked lists are useful for storing collections of data that need to be dynamically resized and accessed in a non-contiguous manner.

      • Inserting a node at the beginning or end of the list
      • Removing a node from the beginning or end of the list
      • Finding the length of the list
      • Traversing the list
      • Searching the list
      • Removing a node from the middle of the list

      With these operations implemented, you can use the SinglyLinkedList class to efficiently store, manipulate, and access data in a linked list.

      Granted, most people prefer to use arrays rather than implementing their own linked list structure these days.

      But implementing a linked list is still one of the most common code exercises in a tech bootcamp or job interview.

      You’ve done a great job learning how to implement a linked list in PHP. Don’t forget to give yourself a treat! 😉

      Also, feel free to use the code in this tutorial for your project.

      Take your skills to the next level ⚡️

      I’m sending out an occasional email with the latest tutorials on programming, web development, and statistics. Drop your email in the box below and I’ll send new stuff straight into your inbox!

      About

      Hello! This website is dedicated to help you learn tech and data science skills with its step-by-step, beginner-friendly tutorials.
      Learn statistics, JavaScript and other programming languages using clear examples written for people.

      Search

      Type the keyword below and hit enter

      Tags

      Click to see all tutorials tagged with:

      Источник