Skip to main content

Types of lists

Lists are another very basic data structure.  Despite that they are actually quite varied.
Essentially a list consists of blocks of memory linked together with pointers.  How they are linked and how they are accessed determines the type of list.

The first distinguishing factor is the number of links.  If there is only one link this is a singly linked list.  Singly linked lists can only be traversed in one direction, but are quite small because they only have one pointer.  Lists with both a forward and back pointer are called double linked lists.  These lists can be traversed both forward and backwards.  Also you can easily delete an element from the center of a list since you have pointers to both the last element and the next element.  Finally there are lists with more than two links.  They generally allow you to traverse your data in more than one way and are only used for specialized purposes.

The second distinguishing factor is the location of the link.  If the link is stored in the element then this is called an endo list.  If the link is stored external to the element then this is an exo list.  Most lists you will encounter are exo lists.  They are slightly more expensive but make up for that by being more flexible.

The last distinguishing factor of lists is where they are accessed.  If you insert and delete at only one end, then the list is a stack.  If you insert at one end and delete from the other then the list is a queue.  If you insert and delete from both ends then this is a dequeue.
Labels:

Comments

Post a Comment

Popular posts from this blog

Duck typing considered harmful.

I've had a chance to work on a fairly large chunk of Python at this point and have decided that Python (like Perl) is completely untenable at scale.  <rant><rave><drool>  but wait!  I have reasons! Programmers spend most of their time reading code.  We read massive amounts of code.  After we read massive amounts of code we write one... or change one... To make a change to a piece of code you first have to understand what it does and how it interacts with the system around it.  Then we start reading massive amounts of code again.  Anything you can do to minimize the amount of code a programmer has to understand to make a change becomes a huge gain in productivity. Duck typing causes the amount of code you need to read to make a change to grow very large. For example lets look at two functions, one in C++ and one in Python. First in C++ int function(type1 arg1, type2 arg2) {   return arg1->method(arg2); } In this fun...
1 comment
Read more

Sieve of Eratosthenes

Another way to generate a list of primes is through the Sieve of Eratosthenes . Essentially you create a long list of numbers starting at 2. 1. Set p equal to 2.  This is your first prime. 2. Cross out every pth number because they are all divisible by p. 3. The first number after p which hasn't been crossed out is the new prime. 4. Repeat from setup 2. As an example lets take the number line from 2 to 10. list = 2, 3, 4, 5, 6, 7, 8, 9, 10 1. p = 2 2. list = 2 , 3, 4 , 5, 6 , 7, 8 , 9, 10 3. p = 3 4. goto 2 2. list = 2 , 3 , 4 , 5, 6 , 7, 8 , 9 , 10 3. p = 5 4. goto 2 2. list = 2 , 3 , 4 , 5, 6 , 7, 8 , 9 , 10 3. p = 7
Post a Comment
Read more

How big are primes?

So, If we were to calculate the first billion primes how much ram would we need? At the end the primes won't fit in a 32bit integer.  If we store them all in 64bit integers we'd need 8GB. Even if they all fit in 32bit integers we'd still need 4GB of storage just to store the list. Seeing at my little machine has 4GB ram that isn't going to work either. How about just storing the intervals between primes? For the first primes (2, 3, 5, 7, 11, 13, 17) we would store (2, 1, 2, 2, 4, 2, 4) Using a byte for every interval less than 128 and a short for the rest lets us store the first billion primes in just about 1GB.  Now that we can do! Maybe we can do even better though...
Post a Comment
Read more