Find it on GitHub
Tag Archives: Data structures
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.
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.
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.
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: 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.
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