PHP 7 Data Structures and Algorithms

PHP 7 Data Structures and Algorithms

by Mizanur Rahman
Released May 2017
Publisher(s): Packt Publishing
ISBN: 9781786463890

Read it now on the O’Reilly learning platform with a 10-day free trial.

O’Reilly members get unlimited access to books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Start your free trial

Book description

Increase your productivity by implementing data structures

About This Book

  • Gain a complete understanding of data structures using a simple approach
  • Analyze algorithms and learn when you should apply each solution
  • Explore the true potential of functional data structures

Who This Book Is For

This book is for those who want to learn data structures and algorithms with PHP for better control over application-solution, efficiency, and optimization.

A basic understanding of PHP data types, control structures, and other basic features is required

What You Will Learn

  • Gain a better understanding of PHP arrays as a basic data structure and their hidden power
  • Grasp how to analyze algorithms and the Big O Notation
  • Implement linked lists, double linked lists, stack, queues, and priority queues using PHP
  • Work with sorting, searching, and recursive algorithms
  • Make use of greedy, dynamic, and pattern matching algorithms
  • Implement tree, heaps, and graph algorithms
  • Apply PHP functional data structures and built-in data structures and algorithms

In Detail

PHP has always been the the go-to language for web based application development, but there are materials and resources you can refer to to see how it works. Data structures and algorithms help you to code and execute them effectively, cutting down on processing time significantly.

If you want to explore data structures and algorithms in a practical way with real-life projects, then this book is for you.

The book begins by introducing you to data structures and algorithms and how to solve a problem from beginning to end using them. Once you are well aware of the basics, it covers the core aspects like arrays, listed lists, stacks and queues. It will take you through several methods of finding efficient algorithms and show you which ones you should implement in each scenario. In addition to this, you will explore the possibilities of functional data structures using PHP and go through advanced algorithms and graphs as well as dynamic programming.

By the end, you will be confident enough to tackle both basic and advanced data structures, understand how they work, and know when to use them in your day-to-day work

Style and approach

An easy-to-follow guide full of examples of implementation of data structures and real world examples to solve the problems faced. Each topic is first explained in general terms and then implemented using step by step explanation so that developers can understand each part of the discussion without any problem.

Table of contents

  1. Preface
    1. What this book covers
    2. What you need for this book
    3. Who this book is for
    4. Conventions
    5. Reader feedback
    6. Customer support
      1. Downloading the example code
      2. Downloading the color images of this book
      3. Errata
      4. Piracy
      5. Questions
  2. Introduction to Data Structures and Algorithms
    1. Importance of data structures and algorithms
    2. Understanding Abstract Data Type (ADT)
    3. Different data structures
      1. Struct
      2. Array
      3. Linked list
      4. Doubly linked list
      5. Stack
      6. Queue
      7. Set
      8. Map
      9. Tree
      10. Graph
      11. Heap
    4. Solving a problem - algorithmic approach
    5. Writing pseudocode
      1. Converting pseudocode to actual code
    6. Algorithm analysis
      1. Calculating the complexity
    7. Understanding the big O (big oh) notation
    8. Standard PHP Library (SPL) and data structures
    9. Summary
  3. Understanding PHP Arrays
    1. Understanding PHP arrays in a better way
      1. Numeric array
      2. Associative array
      3. Multidimensional array
    2. Using an array as flexible storage
    3. Use of multi-dimensional arrays to represent data structures
      1. Creating fixed size arrays with the SplFixedArray method
    4. Performance comparison between a regular PHP array and SplFixedArray
      1. More examples using SplFixedArray
        1. Changing from a PHP array to SplFixedArray
        2. Converting a SplFixedArray to a PHP array
        3. Changing the SplFixedArray size after declaration
        4. Creating a multidimensional array using SplFixedArray
    5. Understanding hash tables
    6. Implementing struct using a PHP array
    7. Implementing sets using a PHP array
    8. Best usage of a PHP array
    9. PHP array, is it a performance killer?
    10. Summary
  4. Using Linked Lists
    1. What is a linked list?
    2. Different types of linked list
      1. Doubly linked lists
      2. Circular linked lists
      3. Multi-linked lists
    3. Inserting, deleting, and searching for an item
      1. Inserting at the first node
      2. Searching for a node
      3. Inserting before a specific node
      4. Inserting after a specific node
      5. Deleting the first node
      6. Deleting the last node
      7. Searching for and deleting a node
      8. Reversing a list
      9. Getting the Nth position element
    4. Understanding complexity for linked lists
    5. Making the linked list iterable
    6. Building circular linked list
    7. Implementing a doubly linked list in PHP
    8. Doubly linked list operations
      1. Inserting at first the node
      2. Inserting at the last node
      3. Inserting before a specific node
      4. Inserting after a specific node
      5. Deleting the first node
      6. Deleting the last node
      7. Searching for and deleting one node
      8. Displaying the list forward
      9. Displaying the list backward
    9. Complexity for doubly linked lists
    10. Using PHP SplDoublyLinkedList
    11. Summary
  5. Constructing Stacks and Queues
    1. Understanding stack
    2. Implementing a stack using PHP array
    3. Understanding complexity of stack operations
    4. Implementing stack using linked list
    5. Using SplStack class from SPL
    6. Real life usage of stack
      1. Nested parentheses matching
    7. Understanding queue
      1. Implementing a queue using PHP array
      2. Implementing a queue using linked list
    8. Using SplQueue class from SPL
    9. Understanding priority queue
      1. Ordered sequence
      2. Unordered sequence
    10. Implementing priority queue using linked list
    11. Implement a priority queue using SplPriorityQueue
    12. Implementing a circular queue
    13. Creating a double - ended queue (deque)
    14. Summary
  6. Applying Recursive Algorithms - Recursion
    1. Understanding recursion
      1. Properties of recursive algorithms
      2. Recursion versus iterative algorithms
      3. Implementing Fibonacci numbers using recursion
      4. Implementing GCD calculation using recursion
    2. Different types of recursions
      1. Linear recursion
      2. Binary recursion
      3. Tail recursion
      4. Mutual recursion
      5. Nested recursion
    3. Building an N-level category tree using recursion
      1. Building a nested comment reply system
    4. Finding files and directories using recursion
    5. Analyzing recursive algorithms
    6. Maximum recursion depth in PHP
    7. Using SPL recursive iterators
    8. Using the PHP built-in function array_walk_recursive
    9. Summary
  7. Understanding and Implementing Trees
    1. Tree definition and properties
    2. Implementing a tree using PHP
    3. Different types of tree structures
      1. Binary tree
      2. Binary search tree
      3. Self-balanced binary search tree
        1. AVL tree
        2. Red-black tree
      4. B-tree
      5. N-ary Tree
    4. Understanding a binary tree
    5. Implementing a binary tree
    6. Creating a binary tree using a PHP array
    7. Understanding the binary search tree
      1. Inserting a new node
      2. Searching a node
      3. Finding the minimum value
      4. Finding the maximum value
      5. Deleting a node
    8. Constructing a binary search tree
    9. Tree traversal
      1. In-order
      2. Pre-order
      3. Post-order
    10. Complexity of different tree data structures
    11. Summary
  8. Using Sorting Algorithms
    1. Understanding sorting and their types
    2. Understanding bubble sort
      1. Implementing bubble sort using PHP
      2. Complexity of bubble sort
      3. Improving bubble sort algorithm
    3. Understanding selection sort
      1. Implementing selection sort
      2. Complexity of selection sort
    4. Understanding insertion Sort
      1. Implementing insertion sort
      2. Complexity of insertion sort
    5. Understanding divide-and-conquer technique for sorting
    6. Understanding merge sort
      1. Implementing merge sort
      2. Complexity of merge sort
    7. Understanding quick sort
      1. Implementing quick sort
      2. Complexity of quick sort
    8. Understanding bucket sort
    9. Using PHP's built-in sorting function
    10. Summary
  9. Exploring Search Options
    1. Linear searching
    2. Binary search
      1. Analysis of binary search algorithm
      2. Repetitive binary search tree algorithm
      3. Searching an unsorted array - should we sort first?
    3. Interpolation search
    4. Exponential search
    5. Search using hash table
    6. Tree searching
      1. Breadth first search
        1. Implementing breadth first search
      2. Depth first search
        1. Implementing depth first search
    7. Summary
  10. Putting Graphs into Action
    1. Understanding graph properties
      1. Vertex
      2. Edge
      3. Adjacent
      4. Incident
      5. Indegree and outdegree
      6. Path
    2. Types of graphs
      1. Directed graphs
      2. Undirected graphs
      3. Weighted graphs
      4. Directed acyclic graphs (DAG)
      5. Representing graphs in PHP
        1. Adjacency lists
        2. Adjacency matrix
    3. Revisiting BFS and DFS for graphs
      1. Breadth first search
      2. Depth first search
    4. Topological sorting using Kahn's algorithm
    5. Shortest path using the Floyd-Warshall algorithm
    6. Single source shortest path using Dijkstra's algorithm
    7. Finding the shortest path using the Bellman-Ford algorithm
    8. Understanding the minimum spanning tree (MST)
    9. Implementing Prim's spanning tree algorithm
    10. Kruskal's algorithm for spanning tree
    11. Summary
  11. Understanding and Using Heaps
    1. What is a heap?
    2. Heap operations
    3. Implementing a binary heap in PHP
    4. Analyzing the complexity of heap operations
    5. Using heaps as a priority queue
    6. Using heap sort
    7. Using SplHeap, SplMaxHeap, and SplMinHeap
    8. Summary
  12. Solving Problems with Advanced Techniques
    1. Memoization
    2. Pattern matching algorithms
    3. Implementing Knuth-Morris-Pratt algorithm
    4. Greedy algorithms
    5. Implementing Huffman coding algorithm
    6. Understanding dynamic programming
    7. 0 - 1 knapsack
    8. Finding the longest common subsequence-LCS
    9. DNA sequencing using dynamic programming
    10. Backtracking to solve puzzle problem
    11. Collaborative filtering recommendation system
    12. Using bloom filters and sparse matrix
    13. Summary
  13. PHP Built-In Support for Data Structures and Algorithms
    1. Built-in PHP features for data structure
      1. Using PHP array
    2. SPL classes
    3. Built-in PHP algorithms
    4. Hashing
    5. Built-in support through PECL
      1. Installation
        1. Interfaces
    6. Vector
    7. Summary
  14. Functional Data Structures with PHP
    1. Understanding functional programming with PHP
      1. First class functions
      2. Higher order functions
      3. Pure functions
      4. Lambda functions
      5. Closures
      6. Currying
      7. Partial applications
    2. Getting started with Tarsana
    3. Implementing stack
    4. Implementing a queue
    5. Implementing a tree
    6. Summary

Product information

  • Title: PHP 7 Data Structures and Algorithms
  • Author(s): Mizanur Rahman
  • Release date: May 2017
  • Publisher(s): Packt Publishing
  • ISBN: 9781786463890