Tag Archives: $_head

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: Detecting and Breaking a Loop in a Linked List

Introduction

Linked lists are one very common and handy data structure that can be used in many cases of the practical programming. In this post we’ll assume that we’re talking about singly linked list. This means that each item is pointed by it’s previous item and it points to it’s next item. In this scenario the first item of the list, its head, doesn’t have an ancestor and the last item doesn’t have a successor.

Singly Linked List
 

Sometimes, due to bugs or bad architecture or complexity of the applications we can have problems with lists. One very typical problem is having a loop, which in breve means that some of the items of the list is pointed twice, as shown on the image below.

Loop in a Singly Linked List
 

So in first place we need to be sure that there is a loop and then: how can we break it!

There are several algorithms on finding a loop, but here’s one very basic. It’s known as the Floyd’s algorithm or the algorithm of the tortoise and hare. Continue reading Computer Algorithms: Detecting and Breaking a Loop in a 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