Avatar of TheRealSami

TheRealSami's solution

to Linked List in the C Track

Published at Sep 26 2019 · 0 comments
Instructions
Test suite
Solution

Note:

This exercise has changed since this solution was written.

Implement a doubly linked list.

Like an array, a linked list is a simple linear data structure. Several common data types can be implemented using linked lists, like queues, stacks, and associative arrays.

A linked list is a collection of data elements called nodes. In a singly linked list each node holds a value and a link to the next node. In a doubly linked list each node also holds a link to the previous node.

You will write an implementation of a doubly linked list. Implement a Node to hold a value and pointers to the next and previous nodes. Then implement a List which holds references to the first and last node and offers an array-like interface for adding and removing items:

  • push (insert value at back);
  • pop (remove value at back);
  • shift (remove value at front).
  • unshift (insert value at front);

To keep your implementation simple, the tests will not cover error conditions. Specifically: pop or shift will never be called on an empty list.

If you want to know more about linked lists, check Wikipedia.

Getting Started

Make sure you have read the "Guides" section of the C track on the Exercism site. This covers the basic information on setting up the development environment expected by the exercises.

Passing the Tests

Get the first test compiling, linking and passing by following the three rules of test-driven development.

The included makefile can be used to create and run the tests using the test task.

make test

Create just the functions you need to satisfy any compiler errors and get the test to fail. Then write just enough code to get the test to pass. Once you've done that, move onto the next test.

As you progress through the tests, take the time to refactor your implementation for readability and expressiveness and then go on to the next test.

Try to use standard C99 facilities in preference to writing your own low-level algorithms or facilities by hand.

Source

Classic computer science topic

Submitting Incomplete Solutions

It's possible to submit an incomplete solution so you can see how others have completed the exercise.

test_linked_list.c

#include <stddef.h>
#include <stdbool.h>
#include "vendor/unity.h"
#include "../src/linked_list.h"

struct list_item **list = NULL;

void setUp(void)
{
   list = new_list();
}

void tearDown(void)
{
   if (list != NULL) {
      delete_list(list);
      list = NULL;
   }
}

void test_new_list(void)
{
   TEST_IGNORE();               // delete this line to run test
   TEST_ASSERT_NOT_NULL(list);
}

void test_is_list_empty_when_empty(void)
{
   TEST_IGNORE();
   TEST_ASSERT_TRUE(is_list_empty(list));
   delete_list(list);
   list = NULL;                 // stop list from dangling
   TEST_ASSERT_TRUE(is_list_empty(list));
}

void test_is_list_empty_when_not_empty(void)
{
   TEST_IGNORE();
   // pre-populate list
   ll_data_t data = 12;
   push(list, data);
   TEST_ASSERT_FALSE(is_list_empty(list));
}

void test_push_with_invalid_list(void)
{
   TEST_IGNORE();
   ll_data_t data = 13;
   TEST_ASSERT_FALSE(push(NULL, data));
}

void test_push_with_valid_list(void)
{
   TEST_IGNORE();
   for (size_t data = 14; data < 19; ++data) {
      TEST_ASSERT_TRUE(push(list, data));
   }
}

void test_pop_returns_list_data(void)
{
   TEST_IGNORE();
   // pre-populate list
   for (size_t data = 11; data <= 15; ++data) {
      push(list, data);
   }
   for (size_t data = 15; data >= 11; --data) {
      TEST_ASSERT_EQUAL(data, pop(list));
   }
}

void test_unshift_with_invalid_list(void)
{
   TEST_IGNORE();
   ll_data_t data = 16;
   TEST_ASSERT_FALSE(unshift(NULL, data));
}

void test_unshift_with_valid_list(void)
{
   TEST_IGNORE();
   for (size_t data = 14; data < 19; ++data) {
      TEST_ASSERT_TRUE(unshift(list, data));
   }
}

void test_shift_returns_list_data(void)
{
   TEST_IGNORE();
   // pre-populate list
   for (size_t data = 12; data < 17; ++data) {
      push(list, data);
   }

   for (size_t data = 12; data < 17; ++data) {
      TEST_ASSERT_EQUAL(data, shift(list));
   }
}

int main(void)
{
   UnityBegin("test/test_leap.c");

   RUN_TEST(test_new_list);
   RUN_TEST(test_is_list_empty_when_empty);
   RUN_TEST(test_is_list_empty_when_not_empty);
   RUN_TEST(test_push_with_invalid_list);
   RUN_TEST(test_push_with_valid_list);
   RUN_TEST(test_pop_returns_list_data);
   RUN_TEST(test_unshift_with_invalid_list);
   RUN_TEST(test_unshift_with_valid_list);
   RUN_TEST(test_shift_returns_list_data);

   UnityEnd();
   return 0;
}

src/linked_list.h

#ifndef _LINKED_LIST_H_
#define _LINKED_LIST_H_

typedef int ll_data_t;

struct list_item {
  ll_data_t value;
  struct list_item* next;
  struct list_item* previous;
};

struct list_item** new_list( void );
int is_list_empty( struct list_item** );
void delete_list( struct list_item** );
int push( struct list_item**, ll_data_t );
ll_data_t pop( struct list_item** );
int unshift( struct list_item**, ll_data_t );
ll_data_t shift( struct list_item** );

#endif

src/linked_list.c

#include "linked_list.h"
#include <stdlib.h>
#include <stdio.h>

/* Creates a new node with the given value and links the created
   node to the previous and next node. Also the backlinks from 
   the input nodes are set if they are not NULL.
*/
static struct list_item* new_node( ll_data_t value,
				    struct list_item* previous_node,
				    struct list_item* next_node )
{
  /* create node */
  struct list_item* node = malloc( sizeof( struct list_item ) );
  node->next = next_node;
  node->previous = previous_node;
  node->value = value;

  /* link the other nodes to this one */
  if( previous_node != NULL )
    previous_node->next = node;
  if( next_node != NULL )
    next_node->previous = node;

  return node;
}

/* Returns the last node in the list. This function assumes that
   the list is not empty.
*/
static struct list_item* get_last_node( struct list_item** list )
{
  struct list_item* cursor = list[ 0 ];
  
  while( cursor->next != NULL )
    cursor = cursor->next;

  return cursor;
}

/* Unlinks the given node from the previous and next node.
   E.g.
   Given the following node sequence: a <-> b <-> c
   If the function is called on b the resulting sequence is
   a <-> c and b points to NULL assuming a and c are not NULL.
   If a is NULL: NULL <- c and NULL <- b -> NULL
   If c is NULL: a -> NULL and NULL <- b -> NULL
*/
static void unlink_node( struct list_item* node )
{
  struct list_item* prev = node->previous;
  struct list_item* next = node->next;

  if( prev != NULL )
    prev->next = next;
  if( next != NULL )
    next->previous = prev;

  node->next = NULL;
  node->previous = NULL;
}

struct list_item** new_list( void )
{
  struct list_item** list = malloc( sizeof( struct list_item* ) );
  list[ 0 ] = NULL;

  return list;
}

int is_list_empty( struct list_item** list )
{
  return ( list == NULL ) ? 1 : list[ 0 ] == NULL;
}

void delete_list( struct list_item** list )
{
  struct list_item* cursor = list[ 0 ];
  
  while( cursor != NULL )
  {
    struct list_item* old = cursor;
    cursor = cursor->next;
    free( old );
  }

  free( list );
}

int push( struct list_item** list, ll_data_t value )
{
  if( list == NULL )
    return 0;
  else if( is_list_empty( list ) )
    list[ 0 ] = new_node( value, NULL, NULL );
  else
    new_node( value, get_last_node( list ), NULL );
  
  return 1;
}

ll_data_t pop( struct list_item** list )
{
  struct list_item* last_node = get_last_node( list );
  ll_data_t last_value = last_node->value;

  /* test if the last node also is the first one */
  if( list[ 0 ] == last_node )
    list[ 0 ] = NULL;

  unlink_node( last_node );
  free( last_node );

  return last_value;
}

int unshift( struct list_item** list, ll_data_t value )
{
  if( list == NULL )
    return 0;
  else if( is_list_empty( list ) )
    list[ 0 ] = new_node( value, NULL, list[ 0 ] );
  
  return 1;
}

ll_data_t shift( struct list_item** list )
{
  struct list_item* first_node = list[ 0 ];
  ll_data_t first_value = first_node->value;

  /* adjust the start of the list */
  list[ 0 ] = first_node->next;

  unlink_node( first_node );
  free( first_node );

  return first_value;
}

Community comments

Find this solution interesting? Ask the author a question to learn more.

What can you learn from this solution?

A huge amount can be learned from reading other people’s code. This is why we wanted to give exercism users the option of making their solutions public.

Here are some questions to help you reflect on this solution and learn the most from it.

  • What compromises have been made?
  • Are there new concepts here that you could read more about to improve your understanding?