Computer Algorithms: Detecting and Breaking a Loop in a Linked List

July 17, 2012algorithms, data structures$_head, algorithms, data, Data structures, Hare, HEAD, Infinite loop, Linked, Linked list, PHP, PointerStoimen

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: Balancing a Binary Search Tree

July 3, 2012algorithms, data structuresB-tree, balanced search tree, binary search, Binary search algorithm, Binary search tree, binary search trees, Binary trees, Computing, Discrete mathematics, Environment, Mathematics, NIL, non-balanced binary search, non-balanced search trees, PHP, Scapegoat tree, search tree, Self-balancing binary search tree, Splay tree, Technology/Internet, TreeStoimen

Introduction

The binary search tree is a very useful data structure, where searching can be significantly faster than searching into a linked list. However in some cases searching into a binary tree can be as slow as searching into a linked list and this mainly depends on the input sequence. Indeed in case the input is sorted the binary tree will seem much like a linked list and the search will be slow.

Inserting into a binary search tree — A binary search tree may seem much like a linked lists if the input is nearly sorted!

To overcome this we must change a bit the data structure in order to stay well balanced. It’s intuitively clear that the searching process will be better if the tree is well branched. This is when finding an item will become faster with minimal effort.

Balanced tree — Searching into a balanced tree is significantly faster than searching into a non-balanced tree!

Since we know how to construct a binary search tree the only thing left is to keep it balanced. Obviously we will need to re-balance the tree on each insert and delete, which will make this data structure more difficult to maintain compared to non-balanced search trees, but searching into it will be significantly faster. Continue reading Computer Algorithms: Balancing a Binary Search Tree →

Computer Algorithms: Binary Search Tree

June 22, 2012algorithms, data structuresB-tree, balanced binary search tree, balanced binary search trees, binary search, Binary search tree, binary search trees, Binary trees, Environment, Extinction, ineffective binary search trees, Linked list, PHP, R-tree, Red-black tree, Scapegoat tree, search operation, search tree, search trees, sequential search, Technology/Internet, TreeStoimen

Introduction

Constructing a linked list is a fairly simple task. Linked lists are a linear structure and the items are located one after another, each pointing to its predecessor and its successor. Almost every operation is easy to code in few lines and doesn’t require advanced skills. Operations like insert, delete, etc. over linked lists are performed in a linear time. Of course on small data sets this works fine, but as the data grows these operations, especially the search operation becomes too slow.

Indeed searching in a linked list has a linear complexity and in the worst case we must go through the entire list in order to find the desired element. The worst case is when the item doesn’t belong to the list and we must check every single item of the list even the last one without success. This approach seems much like the sequential search over arrays. Of course this is bad when we talk about large data sets.

Search over Linked Lists and Arrays — Sequential search over arrays seems much like searching in linked lists and it is a basically ineffective opration!

Continue reading →

Computer Algorithms: Linked List

June 14, 2012algorithms, data structuresB-tree, Bin, Data structures, Data types, Hash table, HEAD, Insert, John, Linked list, List, Null, PHP, Pointer, public $head, Smith, SQL keywords, StackStoimen

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 →

PHP and MySQL Natural Sort

June 7, 2012micro tutorial, PHPalphabetical order, Entertainment/Culture, Mission: Impossible, Mission: Impossible 2, Mission: Impossible 3, MySQL AB, natural sort order, Order by, PHP, Pirates of the Carribean, Sorting, Sorting algorithmsStoimen

Use Case

Let’s say we have an array of data represented by some text followed by a number. Just like the movies from a movie series like “Mission Impossible” or “Pirates of the Carribean”. We know that they are often followed by the consecutive number of the episode.

Mission: Impossible 1
Mission: Impossible 2
Mission: Impossible 3
...

Since we have no more than three or four episodes we can easily sort the array if it’s not sorted initially.

$a = array('Mission: Impossible 2', 'Mission: Impossible 3', 'Mission: Impossible 1');
 
sort($a);
 
// Mission: Impossible 1
// Mission: Impossible 2
// Mission: Impossible 3
print_r($a);

However in some cases we can have more than 10 episodes. Then we can meet a problem while sorting the array above.

$a = array('Episode 1', 'Episode 2', 'Episode 11', 'Episode 112');
 
sort($a);
 
// Episode 1
// Episode 11
// Episode 112
// Episode 2
print_r($a);

Now because this is by default an alphabetical sort order we get an array that isn’t sorted to our human undestanding.

The question is how to overcome this problem?
Continue reading PHP and MySQL Natural Sort →

stoimen's web log

on web development

Computer Algorithms: Detecting and Breaking a Loop in a Linked List

Introduction

Computer Algorithms: Balancing a Binary Search Tree

Introduction

Computer Algorithms: Binary Search Tree

Introduction

PHP and MySQL Natural Sort

Use Case