Wednesday, September 26, 2012

Lists: A brief explanation

So recently I've been asked to try to explain a series of topics needed to have a decent understanding of programming and its constructs. I don't exactly consider myself an expert in all that is programming and this will likely challenge me as well. So where do we start? I thought I'd jump right in and go with Lists, hence the title, surprising right?

So what are lists? I'm sure that you have used lists for a number of things in your everyday life, such as grocery lists, or task lists, or Christmas lists. So to sum it up lists as you know are just a collection of items that can be either ordered or not. At this point if you have a basic understaning of programming you are likely thinking. Well that sounds like an array. And you would be correct. A list and an array are one in the same thing when we talk about programming. Now there are other types of lists that aren't arrays. This brings up so to our actual topic of today.

In the "lists" world we have a few different types of lists that exists. Today I am going to focus on linked lists. In the world of linked lists there are 3 types, single link, double link and circular. Circular isn't exactly a list type as much as a variation on single and double link lists. All this means is that the last element (tail node) is connected to the first element(head node) in such a way that when you attempt to access an element beyond the end of the list that you start back at the beginning. If the list is a circular double link list, then you are also permitted to access the end of the list by attempting to access an element before the start of the list. So lets see what this means exactly.

Single Linked Lists
A single link linked list is a list in which you can iterate from beginning to end and only in that direction. Each node is connected to the next node through a pointer. Lets take a look at an example. Lets say that we have a 3 element(A,B,and C) single linked list that is ordered. You end up with the following list.

A -> B -> C

You can see here that you start at node A and end with node C. This is very important, since unlike arrays, a linked list cannot begin iterating from arbitrary points within the list. They must start with the head or tail node. Unfortunately unless you are looking for value in the tail node in a single linked list, starting there is a bit pointless since you can't iterate backwards through the list. Now I'm sure you are thinking, 'what about circular linked lists? Certainly those would make the end node a reasonable place to start?'. While, you can start with the tail node in a circular single linked list, if you aren't looking for the end node it makes more sense to start with the head node and save yourself an iteration.

Now what if we want the ability to move backwards through the list? Yup, you guessed it, double linked lists. Now this is gonna be hard to understand so bear with me, we need to make sure that the nodes connect to the node before them. This would be represented with a similar graph to the previous example except it now goes in 2 directions.

A <-> B <-> C

That's insane right? Also notice here that we can start at the head or tail nodes and iterate over the list. We can still only start at the head or tail nodes, but now the list can be iterated over in 2 directions.

So now we understand the basic concept of the linked list. But how in the world do we translate that into code? Well first of all, the best way I know of to translate this is by using and Object Oriented approach. I'm sure its possible to accomplish using a non object oriented approach but I'm not sure it would look nearly as nice. For this example I will go with how to implement this in Java. If that's not your flavor worry not, for I will be adding implementations of this in other languages later on. Now for the linked list that in this example we are going to have it hold integer values to keep it simple. There are better ways to do this but those topics are beyond the scope of this post.

Java


class Node{
private Node prev;
private Node next;
private int val;

public Node(Node prev, Node next, int value){
this.prev = prev;
this.next = next;
this.val = value;
}

public void setValue(int value){
this.val = value;
}

public int getValue(){
return this.val;
}

public void setNext(Node node){
this.next = node;
}

public Node getNext(){
return this.next;
}

public void setPrev(Node node){
this.prev = node;
}

public Node getPrev(Node node){
return this.prev;
}

public void remove(){
this.prev.setNext(this.next);
this.next.setPrev(this.prev);
}

public void addAfter(Node node){
this.prev = node;
this.next = node.getNext();
this.prev.setNext(this);
}
}

Perl Sessions...filling in the gaps

I recently had to utilize the perl CGI::Session module and found the documentation a little odd and somewhat vague in certain areas. So for my sanity and hopefully anyone else that runs across this, I'm going to take a moment to explain how to use this module so that you too can get up and running quick.

Sessions...How do they work?

Sessions are fairly basic, the goal is to store some information on the client that will allow us to work around the Internet being stateless. Now there are only a couple ways to do this. The first way is the most common method of storing the user's session id in a cookie. But what if the user doesn't accept cookies? Well that would make the first method a bit hard now wouldn't it? Luckily we can always fall back on storing the user's session id in a hidden variable within the page. The Session module handles sessions in this way as well by defaulting to using cookies. Now I'm sure you are thinking, well great so you have an id for the user's session. But how do we use it? At this point you need to track the user on the server. To do this you can either:
  • save the session data to a file
    or
  • store the session data in a database table with the session id as the primary key.
Getting started:

Before we can use the Sessions module we need to make sure we have included both the CGI and the CGI::Session module. We also need an instance of the CGI object. The code to this is as follows:

use CGI qw/:standard/; # for parsing form data
use CGI::Session qw/-ip-match/;
my $cgi = new CGI();

Now that we have added the modules we can start a session. First, we usually want to make sure that the user doesn't already have a session open. To do this we use the following.

my $session_id = $cgi->cookie('session_name') || $cgi->param('session_name') || undef;

You see in the first thing we check is if there is a cookie in place with the name assigned to identify it with $cgi->cookie('session_name'). If there isn't one then we may want to check to make sure that there wasn't a hidden variable passed to the server with the session_id. Now that we know that we have the session_id set we can create a new session.

my $session = new CGI::Session("driver:File", $session_id, {Directory=>'/tmp'});

Here we are passing a few parameters to the Session() function.
  1. Driver : This parameter is used to define how the data will be stored. In this instance the data will be stored in a file.
  2. Session ID : The users session id. If the user already has a session open then this will use that users session. If it doesn't however, then the module will start a new session.
  3. Directory : This is used to specify what directory the module should save sessions to.
There is a lot more to the module than what I have explained here. You can get the full CPAN documentation here .