Doubly linked list

A doubly linked list is like our previously implemented Linked List, but instead of only having pointers to the next element, it also has pointers to the previous element:

610px-Doubly-linked-list.svg

This property makes the doubly linked list very useful as a base for other data structures such as the stack: having a previous pointer means we can quickly (O(1)) remove objects from the list’s tail, which would be impossible with a linked list.

We won’t discuss implementation since it so similar to a linked list. If anything implementation is even simpler than a linked list because of the previous pointer access.

Full source code with printable tests follows below, and can also be found at out github.

/*
    File: doubly_linked_list.c

    Copyright (c) 2014 Leonardo Brito <lbrito@gmail.com>

    This software is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation; either version 2 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License along
    with this program; if not, write the Free Software Foundation, Inc., 51
    Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "comparators.c"

#if !defined _TEST_SIZE_LIST && defined _DEBUGGING
#define _TEST_SIZE_LIST 10
#endif

#define TRUE 1
#define FALSE 0

typedef struct d_element
{
      void *data;
      struct d_element *next, *prev;
} d_element;

typedef struct d_linked_list
{
      d_element *head;
      d_element *tail;
      unsigned size;
      int (*cmp) (void*, void*);
} d_linked_list;

/**
 *  @brief create a new doubly linked list
 *
 *  @param [in] comparator
 *  @return
 */
d_linked_list *new_list(int (*comparator) (void*, void*))
{
      d_linked_list *l = malloc(sizeof(d_linked_list));
      l->size = 0;
      l->cmp = comparator;
      return l;
}

/**
 *  @brief create a new d_element
 *
 *  @param [in] data
 *  @return
 */
d_element *new_d_element(void *data)
{
      d_element *e = (d_element*) malloc(sizeof(d_element));
      e->data = data;
      e->next = NULL;
      e->prev = NULL;
      return e;
}

/**
 *  @brief add data to list
 *
 *  @param [in] list
 *  @param [in] data
 */
void add(d_linked_list *list, void *data)
{
      if (list->size == 0)
      {
            list->head = new_d_element(data);
            list->tail = list->head;
      }
      else
      {
            d_element *toadd = new_d_element(data);
            list->tail->next = toadd;
            toadd->prev = list->tail;
            list->tail = toadd;
      }
      ++list->size;
}

/**
 *  @brief search for data in list
 *
 *  @param [in] list
 *  @param [in] data
 *  @return searched element
 */
d_element *search(d_linked_list *list, void *data)
{
      d_element *e = list->head;
      do
      {
            if (list->cmp(data, e->data) == 0) return e;
      } while ((e = e->next) != NULL);
      return NULL;
}

/**
 *  @brief delete data from list
 *
 *  @param [in] list
 *  @param [in] data
 *  @return TRUE if data was found & deleted, FALSE otherwise
 */
int delete(d_linked_list *list, void *data)
{
      d_element *searched = search(list, data);
      if (searched)
      {
            int ishead = !list->cmp(searched->data, list->head->data);
            if (!ishead)
            {
                  if (searched != NULL)
                  {
                        searched->next->prev = searched->prev;
                        searched->prev->next = searched->next;
                  }
                  else
                  {
                        list->head = NULL;      // LAST ELEMENT IN LIST
                        list->tail = NULL;
                  }
            }
            else
            {
                  if (list->head->next != NULL)
                  {
                        list->head = list->head->next;
                        list->head->prev = NULL;
                  }
                  else
                  {
                        list->head = NULL;      // LAST ELEMENT IN LIST
                        list->tail = NULL;
                  }
            }
            free(searched->data);
            free(searched);
            --list->size;
            return TRUE;
      }
      else return FALSE;
}

#ifdef _DEBUGGING

d_linked_list *build_list()
{
      d_linked_list *list = new_list(compare_string);
      char *basetext = "I'm d_element number ";
      int i=1;
      for (;i<_TEST_SIZE_LIST;i++)
      {
            char *text1 = malloc(sizeof(char)*(strlen(basetext)+10));
            strcpy(text1, basetext);
            char numb[10];
            sprintf(numb, "%d", i);
            strcat(text1, numb);
            add(list, text1);
      }

      return list;
}

void print_list(d_linked_list *list)
{
      if (list->size == 0)
      {
            printf("\nList empty.");
      }
      else
      {
            printf("\n==============");
            d_element *e = list->head;
            int i = 0;
            do
            {
                  printf("\nList [%d]:\t%s",i++,(char*)e->data);
            } while ((e = e->next) != NULL);
            printf("\n==============\n");
      }
}

void test_delete(d_linked_list *list, int eln)
{
      char data[20];
      sprintf(data, "I'm d_element number %d", eln);
      if (delete(list, data)) printf("\nSuccessfully deleted d_element #%d, %d elems in list",eln,list->size);
      else printf("\nElem #%d not found",eln);
}

void test_add(d_linked_list *list, int eln)
{
      char *data = malloc(sizeof(char)*50);
      sprintf(data, "I'm NEW d_element number %d", eln);
      add(list, data);
      printf("\nSuccessfully added NEW d_element #%d, %d elems in list",eln,list->size);
}

int main()
{
      d_linked_list *list = build_list();

      print_list(list);
      test_delete(list, 1);
      test_delete(list, 2);
      test_delete(list, 7);
      test_delete(list, 3);
      test_delete(list, 4);
      test_delete(list, 5);
      test_add(list, 13);
      test_delete(list, 6);
      test_delete(list, 8);
      test_delete(list, 9);
      print_list(list);
      test_add(list, 1337);
      print_list(list);
      test_delete(list, 2);
      test_add(list, 98);
      print_list(list);

      return 0;
}

#endif
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s