# 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

## 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.

# Use fopen() to Check File Availability?

## Zend Framework and Zend_Http_Client

I’ve posted about Zend_Http_Client. Simply there you can ‘make’ your own http client and you can request a remote file. Just to check what’s going on with this file.

```// new HTTP request to a file \$httpClient = new Zend_Http_Client('http://www.example.com/myfile.mp4');   // get the HEAD of the response and match agains the // Content-Length. That's because using the Content-Type is slower \$response = \$httpClient->request(Zend_Http_Client::HEAD);   // if the Content-Length is 0 the file doesn't exists if (0 === (int)\$response->getHeader('Content-Length')) { echo 'the file doesn\'t exits'; }```

However is there any other way to answer the same question?

## fopen()

Yes and no? Perhaps yes, but you should be careful. I’m still not sure it can be used in any case. However here’s the snippet.

```if (FALSE === @fopen('http://www.example.com/myfile.mp4', 'r')) { echo 'the file doesn\'t exists'; }```

fopen() will return FALSE whenever the file doesn’t exists.

In both cases I request a remote file – an MPEG-4 file. Note that fopen()’s first parameter can be a HTTP resource.

# Read Remote File Content-Type with Zend_Http_Client

## Check an Image on a Remote Server

This is a common task. You’d like to know whether the image on the remote server exists. Zend Framework gives the answer of this question and in particular this can be completed with Zend_Http_Client.

## Content-Type and Content-Length

The little problem is that checking for content-type is not always correct, because it will return an image content type even when the image does not exists, so it’s better to check for content-length.

## Code

The simple way to check this is like that:

```\$client = new Zend_Http_Client('http://remote-machine/image.jpg'); \$response = \$client->request('head'); if ( NULL == \$response->getHeader('Content-Length') ) // do whatever if the image does not exists.```

In fact here, in this example I don’t check for GET request, because is way to slow than the HEAD method, but you should be aware of incorrect responses when using HEAD. In fact if you request the HEAD of a FLV video it will be returned text content-type, while using GET everything’s working fine but slow though.