lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]

> -------- Original Message --------
> Date: Wed, 16 Feb 2011 08:07:39 +0100
> From: Axel Kittenberger <>
> Subject: Re: Propsoal: a lua dialect without nil
> To: Lua mailing list <>
> Message-ID:
> 	<>
> Content-Type: text/plain; charset=windows-1252
> ...I don't see how a static typed
> language could work without null pointers. How would it cap linked
> lists? It would need some sort of singleton as cap marker, not there
> marker, etc. which would eventually boil down to the same as if it
> would be 0.

Circular lists accomplish that without NULL and without a singleton. The
"head" of the list acts as the "anchor" for the list (and also as a
sentinel). The doubly-linked circular list is especially nice because
you can just copy pointers around without special cases for NULL, which
avoids branch-prediction problems (and also makes implementation less

The "tricky" parts are: making sure every node is initialized properly,
and to remember *not* to test for NULL when iterating.

I've used them frequently, especially when I want to add a linked list
to a library without creating a dependency to a more general list

Unfortunately, it's hard to get people on board with circular lists
because most programmers are used to checking for NULL, and the circular
list throws them for a loop.

A brief search didn't turn up (what I felt was) a nice example, so I
whipped up a sample file. It builds and runs (at least in MS VC++).

//Circular doubly linked list sample. NOTE: NOT THOROUGHLY TESTED.
#include <stdlib.h>
#include <stdio.h>
#include <conio.h>

typedef struct CLIST
    struct CLIST *pPrev;
    struct CLIST *pNext;
    int x;

void clist_init(CLIST *p, int x)
    p->pPrev = p->pNext = p;
    p->x = x;

void clist_link(CLIST *p, CLIST *pPredecessor)
    p->pPrev = pPredecessor;
    p->pNext = pPredecessor->pNext;
    pPredecessor->pNext->pPrev = p;
    pPredecessor->pNext = p;

void clist_unlink(CLIST *p)
    p->pPrev->pNext = p->pNext;
    p->pNext->pPrev = p->pPrev;
    p->pPrev = p->pNext = p;

static CLIST anchor;
static CLIST node1;
static CLIST node2;
static CLIST node3;

int main(int argc, char *argv[])
    CLIST *p;


    clist_link(&node1, &anchor);
    clist_link(&node2, &node1);
    clist_link(&node3, &node2);

    printf("Initial node list:\n"); //note: does not include "anchor"
    for (p=anchor.pNext; p!=&anchor; p=p->pNext)

    printf("\nRemove node 2 and the result is:\n");
    for (p=anchor.pNext; p!=&anchor; p=p->pNext)

    printf("\nRe-link node 2 after node 3 to get:\n");
    clist_link(&node2, &node3);
    for (p=anchor.pNext; p!=&anchor; p=p->pNext)

    printf("\nDone. Press any key...");

    return EXIT_SUCCESS;

John Giors
Independent Programmer
Three Eyes Software