Tag Archives: Hash table

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: Rabin-Karp String Searching

Introduction

Brute force string matching is the a very basic sub-string matching algorithm, but it’s good for some reasons. For example it doesn’t require preprocessing of the text or the pattern. The problem is that it’s very slow. That is why in many cases brute force matching can’t be very useful. For pattern matching we need something faster, but to understand other sub-string matching algorithms let’s take a look once again on brute force matching.

In brute force sub-string matching we checked every single character from the text with the first character of the pattern. Once we have a match between them we shift the comparison between the second character of the pattern with the next character of the text, as shown on the picture below.

Brute Froce Principles
Brute force string matching is slow because it compares every single character from the pattern and the text!
Continue reading Computer Algorithms: Rabin-Karp String Searching

Make your own link shortener

Why you should do that?

First of all what’s a link shortener? Such online software exists and it’s widely used by the customers. Sites like bit.ly became extremely popular because of the growth of web apps like Facebook and especially Twitter. The simple goal that they achieve is to convert a long website uri into a short unique one. Beside that they give more information about who clicked that link and some useful stats along with that.

The question is why to make your own link shortener? One of the main reasons why is to paste links containing in plaintext your domain. In the case of http://stoimen.com instead of using http://bit.ly/xxxxx it will be great if the link was something like http://stoimen.com/xxxx than pasting it into Twitter or wherever I get the primary impression of my domain.

How to …

It should be no mystery how to make your own. In fact you’ll need only one more table into the database, as this is the most common way to achieve it. Of course you can do that with no database using the file system to store the hash table in whatever format you’d like.

In the case of the DB solution you can simply make a table with three columns containing the unique id of the row, the short and the full link. Thus requesting some short link the db will return the “real” full uri. You can simply drop the short column if you’d like more efficient solution. Thus the unique identifier may become short link. That may be really fast if you’ve an index on the full link column.

See the example below:

id | short_link | full_link
1  | qwrt 	| /blog/2010/01/27/theory-of-caching-zend_cache-zend-optimizer