Tag Archives: Stack

PHP: Arrays or Linked Lists?

Arrays vs. Linked List

If we talk about arrays and linked lists we know the pros and cons about both of them. No matter which programming language we use arrays benefit from direct access to its items, while linked lists are more memory efficient for particular tasks.

Array & Linked List
Array & Linked List

The items of a linked list keep a reference to their successor, so we can easily walk through the entire list. However we don’t have direct access to its elements. Thus we can’t go directly to its middle element! Even more – in particular implementations of a linked list we don’t know its length. But in some cases linked lists are far more effective than arrays. For instance reversing an array of non-numeric values require constant additional memory, but also requires n/2 exchanges. The same taks using linked lists is not only performed in linear time, but doesn’t require any additional memory. The only thing we need to do is to reverse the links – no movement of values and the items remain at the same place in the memory.

Merging of two arrays often require more space (proportional of the space of the two arrays) or many exchanges in case we try to do it in place. The same task on linked lists is far more effective with only changing pointers and without moving the values. Continue reading PHP: Arrays or Linked Lists?

Computer Algorithms: Linked List

Introduction

The linked list is a data structure in which the items are ordered in a linear way. Although modern programming languages support very flexible and rich libraries that works with arrays, which use arrays to represent lists, the principles of building a linked list remain very important. The way linked lists are implemented is a ground level in order to build more complex data structures such as trees.

It’s true that almost every operation we can perform on a linked list can be done with an array. It’s also true that some operations can be faster on arrays compared to linked lists.

However understanding how to implement the basic operations of a linked list such as INSERT, DELETE, INSERT_AFTER, PRINT and so on is crucial in order to implement data structures as rooted trees, B-trees, red-black trees, etc.

Overview

Unlike arrays where we don’t have pointers to the next and the previous item, the linked list is designed to support such pointers. In some implementations there is only one pointer pointing to the successor of the item. This kind of data structures are called singly linked lists. In this case the the last element doesn’t have a successor, so the pointer to its next element usualy is NULL. However the most implemented version of a linked list supports two pointers. These are the so called doubly linked lists.

Arrays vs. linked list
Arrays items are defined by their indices, while the linked list item contains a pointer to its predecessor and his successor!
Continue reading Computer Algorithms: Linked List

Computer Algorithms: Stack and Queue

Introduction

Every developer knows that computer algorithms are tightly related to data structures. Indeed many of the algorithms depend on a data structures and can be very effective for some data structures and ineffective for others. A typical example of this is the heapsort algorithm, which depends on a data structure called “heap”. In this case although the stack and the queue are data structures instead of pure algorithms it’s imporant to understand their structure and the way they operate over data.

However, before we continue with the concrete realization of the stack and the queue, let’s first take a look on the definition of this term. A data structure is a logical abstraction that “models” the real world and presents (stores) our data in a specific format. The access to this data structure is often predefined thus we can access directly every item containing data. This help us to perform a different kind of tasks and operations over different kind of data structures – insert, delete, search, etc.. A typical data structures are the stack, the queue, the linked list and the tree.

All these structures help us perform specific operations effectively. For instance searching in a balanced tree is faster than searching in a linked list.

It is also very important to note that data structures can be represented in many different ways. We can model them using arrays or pointers, as shown in this post. In fact the most important thing is to represent the logical structure of the data structure you’re modeling. Thus the stack is a structure that follows the LIFO (Last In First Out) principle and it doesn’t matter how it is represented in our program (whether it will be coded with an array or with pointers). The important thing into a stack representation is to follow the LIFO principle correctly. In this case if the stack is an array only its top should be accessible and the only operation must be inserting new top of the stack.
Continue reading Computer Algorithms: Stack and Queue

Friday Algorithms: A Data Structure: JavaScript Stack

Algorithms and Data Structures

stack

Instead of writing about “pure” algorithms this time I’ve decided to write about data structures and to start with a stack implementation in JavaScript. However algorithms and data structures live together since the very beginning of the computer sciences. Another reason to write about data structures is that many algorithms need a specific data structure to be implemented. Most of the search algorithms are data structure dependent. You know that searching into a tree is different from searching into a linked list.

I’d like to write more about searching in my future algorithm posts, but first we need some data structure examples. The first one is, as I mentioned – stack.

Implemented in JavaScript this is really a simple example, which don’t need much to be understood. But in first place what is a stack?

You can thing of the “computer science” stack as a stack of sheets of paper, as it’s shown on the picture. You’ve three basic operations. You can add new element to the stack by putting it on the top of the stack, so the previous top of the stack becomes the second element in the stack. Another operation is to “pop” from the stack – remove the “first” element in the stack – the top most element, and to return it. And finally print the stack. This is difficult to define as an operation, but let say you’ve to show somehow every element from the stack.

Here’s a little diagram:

Stack

Source Code

At the end some source code:

var node = function()
{
    var data;
    var next = null;
}
 
var stack = function()
{
    this.top = null;
 
    this.push = function(data) {
        if (this.top == null) {
            this.top = new node();
            this.top.data = data;
        } else {
            var temp = new node();
            temp.data = data;
            temp.next = this.top;
            this.top = temp;
        }
    }
 
    this.pop = function() {
        var temp = this.top;
        var data = this.top.data;
        this.top = this.top.next;
        temp = null;
        return data;
    }
 
    this.print = function() {
        var node = this.top;
        while (node != null) {
            console.log(node.data);
            node = node.next;
        }
    }
}
 
var s = new stack();
 
s.push(1);
s.push(2);
s.push(3);
 
s.print();
 
var a = s.pop();
 
s.print();