XOR Linkedlist

Problem:


Implement a doubly linked list with a single pointer.


Solution:

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

        /* pray that a long is the size of a struct link* */

        typedef unsigned long pointer;
        struct link
        {
          pointer next_prev;
          int payload;
        };

        typedef struct link link;
        link* add_data(int payload, struct link* list)
        {
          struct link * new_link = (struct link*)malloc(sizeof(link));
          assert(new_link);
          new_link->next_prev = (pointer)list;
          new_link->payload = payload;
          if (list != NULL)
          {
            list->next_prev = (pointer) list->next_prev ^ (pointer)new_link;
          }
          return new_link;
        }

        void walk_list(link *list)
        {
          struct link* prev = 0;
          while (list != NULL)
          {
            pointer next = ((pointer)prev) ^ list->next_prev;
            printf("%d ", list->payload);
            prev = (struct link*)list;
            list = (link*)next;
          }
          printf("\n");
        }

        int main(void)
        {
          link *l1 = add_data(1, NULL);
          link *l2 = add_data(2, l1);
          /* add something to the front ... */
          /* add something to the back ... */
          link *l3 = add_data(3, l2);
          link *l4 = add_data(4, l3);
          link *l5 = add_data(5, l4);

          /* walk from front to back */
          walk_list(l1);
          /* walk from back to front */
          walk_list(l5);

          return 0;
        }