Just Learn Code

Exploring Singly Linked Lists in PHP: Implementation and Operations

Introduction to Singly Linked List in PHP

When it comes to designing and implementing data structures, linked lists are a popular choice for many programmers. A linked list is a collection of nodes, where each node contains a value and a reference to the next node.

In contrast to arrays, linked lists allow for constant-time insertions and deletions, making them incredibly useful in certain contexts. In this article, we’ll be exploring the world of singly linked lists in PHP.

We’ll start by examining some of the basic terminology associated with linked lists. From there, we’ll look at how to implement a singly linked list in PHP, and cover some essential operations that you can perform on a singly linked list.

Linked List Terminology and Illustration

Before we dive into the specifics of singly linked lists, it’s essential to understand some basic terminology associated with linked lists. Here are some of the key terms you should be familiar with:

– Node: A single element of a linked list, containing data and a reference to the next node.

– Head: The first node in a linked list. – Tail: The last node in a linked list.

– Link: The reference contained in each node that points to the next node in the list. – Length: The number of nodes in the list.

To better illustrate the structure of a singly linked list, imagine a chain of people holding hands. Each person represents a node, while their hands represent the links between nodes.

The first person in the chain represents the head of the list, while the last person represents the tail.

Implementing a Singly Linked List in PHP

In PHP, we can implement a singly linked list using two classes: a Node class to represent individual nodes, and a SinglyLinkedList class to represent the overall list. Here’s what the Node class might look like:

“`

class Node {

public $data;

public $next;

public function __construct($data) {

$this->data = $data;

$this->next = null;

}

}

“`

The Node class has two properties: `$data`, which holds the value contained in the node, and `$next`, which holds a reference to the next node in the list.

The `__construct` method is called when we create a new node and sets the node’s data to the value we pass in. Next, let’s look at the SinglyLinkedList class:

“`

class SinglyLinkedList {

private $head;

private $tail;

private $length;

public function __construct() {

$this->head = null;

$this->tail = null;

$this->length = 0;

}

}

“`

The SinglyLinkedList class has three properties: `$head`, which holds a reference to the first node in the list, `$tail`, which holds a reference to the last node in the list, and `$length`, which keeps track of the number of nodes in the list.

The `__construct` method is called when we create a new linked list and initializes the properties to their starting values.

Basic Operations on Singly Linked List

With a basic understanding of singly linked lists and how to implement them in PHP, let’s move on to some of the fundamental operations you can perform on a singly linked list.

Inserting a Node at the Beginning of the List

To insert a new node at the beginning of a singly linked list, we can use the `push` method:

“`

public function push($data) {

$newNode = new Node($data);

if ($this->head === null) {

$this->head = $newNode;

$this->tail = $newNode;

} else {

$newNode->next = $this->head;

$this->head = $newNode;

}

$this->length++;

}

“`

The `push` method creates a new node and adds it to the beginning of the list by setting the new node’s `$next` property to the current head of the list. If the list is empty, we set both the head and tail properties to the new node.

Finally, we increment the length of the list.

Inserting a Node at the End of the List

To insert a new node at the end of a singly linked list, we can use the `append` method:

“`

public function append($data) {

$newNode = new Node($data);

if ($this->head === null) {

$this->head = $newNode;

$this->tail = $newNode;

} else {

$this->tail->next = $newNode;

$this->tail = $newNode;

}

$this->length++;

}

“`

The `append` method works similarly to `push`, but instead of adding the new node to the beginning of the list, it adds it to the end. If the list is empty, it creates a new head and tail.

Otherwise, it sets the current tail’s `$next` property to the new node and updates the tail to the new node.

Removing a Node from the Beginning of the List

To remove the first node in a singly linked list, we can use the `pop` method:

“`

public function pop() {

if ($this->head === null) {

return null;

}

$removedNode = $this->head;

if ($this->head === $this->tail) {

$this->tail = null;

}

$this->head = $this->head->next;

$this->length–;

return $removedNode->data;

}

“`

The `pop` method checks if the head of the list exists. If the list is empty, it returns null.

Otherwise, it stores a reference to the first node in the list, updates the head to the second node, and decrements the length. Finally, it returns the value contained in the removed node.

Removing a Node from the End of the List

To remove the last node in a singly linked list, we can use the `unshift` method:

“`

public function unshift() {

if ($this->head === null) {

return null;

}

$removedNode = $this->tail;

if ($this->head === $this->tail) {

$this->head = null;

} else {

$currentNode = $this->head;

while ($currentNode->next !== $this->tail) {

$currentNode = $currentNode->next;

}

$this->tail = $currentNode;

$this->tail->next = null;

}

$this->length–;

return $removedNode->data;

}

“`

The `unshift` method checks if the head of the list exists. If the list is empty, it returns null.

Otherwise, it stores a reference to the last node in the list, updates the tail to the second-last node, and decrements the length. Finally, it returns the value contained in the removed node.

Finding the Length of the List

To find the length of a singly linked list, you can use the `$length` property:

“`

public function length() {

return $this->length;

}

“`

The `length` method simply returns the value of the `$length` property, which keeps track of the number of nodes in the list.

Traversing the List

To traverse a singly linked list and print out all the values contained in the nodes, we can use the `traverse` method:

“`

public function traverse() {

$currentNode = $this->head;

while ($currentNode !== null) {

echo $currentNode->data . ‘ ‘;

$currentNode = $currentNode->next;

}

echo “n”;

}

“`

The `traverse` method starts at the head of the list and prints out the value of each node in turn until it reaches the end of the list.

Searching the List

To search a singly linked list for a specific value, we can use the `search` method:

“`

public function search($value) {

$currentNode = $this->head;

while ($currentNode !== null) {

if ($currentNode->data === $value) {

return $currentNode;

}

$currentNode = $currentNode->next;

}

return null;

}

“`

The `search` method starts at the head of the list and looks at each node’s value until it finds a node that matches the specified value. If it finds a matching node, it returns that node.

Otherwise, it returns null.

Removing a Node from the Middle of the List

To remove a node from the middle of a singly linked list, we need to search for the node and then update its previous node’s `$next` property to point to its next node:

“`

public function splice($value) {

$currentNode = $this->head;

$previousNode = null;

while ($currentNode !== null) {

if ($currentNode->data === $value) {

if ($previousNode === null) {

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

} else {

$previousNode->next = $currentNode->next;

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

$this->tail = $previousNode;

}

}

$this->length–;

return $currentNode->data;

}

$previousNode = $currentNode;

$currentNode = $currentNode->next;

}

return null;

}

“`

The `splice` method searches for the specified value and then updates the `$next` property of the previous node to skip over the removed node. If the removed node is the head, we update the head property.

If it’s the tail, we update the tail property.

Conclusion

In conclusion, singly linked lists are a powerful tool for efficiently storing and manipulating data in PHP. By understanding the terminology and basic operations associated with linked lists, you can better leverage this data structure to work more efficiently with your PHP programs.

With a little bit of practice, you’ll be well on your way to mastering the art of singly linked lists in PHP!

3) SinglyLinkedList Class code

Now that we’ve covered the basics of singly linked lists in PHP, let’s take a closer look at the implementation of all the operations we’ve discussed. The code below combines all the methods we’ve covered so far into a single `SinglyLinkedList` class:

“`

class SinglyLinkedList {

private $head;

private $tail;

private $length;

public function __construct() {

$this->head = null;

$this->tail = null;

$this->length = 0;

}

public function push($data) {

$newNode = new Node($data);

if ($this->head === null) {

$this->head = $newNode;

$this->tail = $newNode;

} else {

$newNode->next = $this->head;

$this->head = $newNode;

}

$this->length++;

}

public function append($data) {

$newNode = new Node($data);

if ($this->head === null) {

$this->head = $newNode;

$this->tail = $newNode;

} else {

$this->tail->next = $newNode;

$this->tail = $newNode;

}

$this->length++;

}

public function pop() {

if ($this->head === null) {

return null;

}

$removedNode = $this->head;

if ($this->head === $this->tail) {

$this->tail = null;

}

$this->head = $this->head->next;

$this->length–;

return $removedNode->data;

}

public function unshift() {

if ($this->head === null) {

return null;

}

$removedNode = $this->tail;

if ($this->head === $this->tail) {

$this->head = null;

} else {

$currentNode = $this->head;

while ($currentNode->next !== $this->tail) {

$currentNode = $currentNode->next;

}

$this->tail = $currentNode;

$this->tail->next = null;

}

$this->length–;

return $removedNode->data;

}

public function length() {

return $this->length;

}

public function traverse() {

$currentNode = $this->head;

while ($currentNode !== null) {

echo $currentNode->data .

‘ ‘;

$currentNode = $currentNode->next;

}

echo “n”;

}

public function search($value) {

$currentNode = $this->head;

while ($currentNode !== null) {

if ($currentNode->data === $value) {

return $currentNode->data;

}

$currentNode = $currentNode->next;

}

return null;

}

public function splice($value) {

$currentNode = $this->head;

$previousNode = null;

while ($currentNode !== null) {

if ($currentNode->data === $value) {

if ($previousNode === null) {

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

} else {

$previousNode->next = $currentNode->next;

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

$this->tail = $previousNode;

}

}

$this->length–;

return $currentNode->data;

}

$previousNode = $currentNode;

$currentNode = $currentNode->next;

}

return null;

}

}

“`

In addition to the `__construct` method, which sets up the initial state of the linked list, this code includes methods for pushing, appending, popping, unshifting, finding the length of the list, traversing the list and printing out its values, searching for a specific value in the list, and splicing out a node with a specified value.

4) Importance of Singly Linked List in Data Structures

Linked lists are an essential data structure for software programmers. They offer excellent benefits over arrays.

In particular, arrays require an expensive computational cost when items are shifted, inserted, or deleted. This is because all the array’s subsequent items need to be re-indexed.

Linked lists, on the other hand, allow for constant-time insertions and deletions. Linked lists are a fundamental building block for more complicated data structures such as stacks, queues, and hash tables, among other advantages.

Other Operations on a Linked List

In addition to the standard insertions, deletions, and queries that we have discussed so far, there are many other operations that can be performed on a linked list. Deleting a node, reversing a list, merging two lists, and sorting a list are some of the operations that can be performed in a linked list.

Application of Singly Linked List

Singly linked lists are fundamental to computer science and software engineering. They are used in various fields like software development, telecommunications, operating systems, finance, and many more.

For instance, in data-driven applications, linked lists are used to insert, delete, and look up items in a collection of data. Similarly, real-time components of operating systems like signal handlers use linked lists to keep track of tasks and queues.

In telecommunications, a linked list is used to store information related to the call chain. This chain tracks the sequence of calls when a customer makes a call.

Along with recording the call duration and other metadata, it handles customer billing. In software engineering, enumerated linked lists are used to traverse a tree-like data structure, performing various operations like sorting and deleting nodes during the traversal process.

Conclusion

In conclusion, singly linked lists are a powerful and efficient data structure frequently used in programming languages like PHP. We have explored the fundamental terminologies associated with the linked lists and their implementation, cover all essential operations such as push, append, pop, unshift, length, traverse, search, and splice.

We have also seen the importance of linked lists in modern computer science and software engineering fields and their real-life applications. So, if you are looking to work with data-driven applications, linked lists are an essential tool that should never be overlooked.

In summary, this article provided an in-depth overview of singly linked

Popular Posts