Avatar of okamotonr

okamotonr's solution

to Linked List in the C Track

Published at Sep 09 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;
   }
}

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

static 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));
}

static 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));
}

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

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

static 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));
   }
}

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

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

static 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);

   return UnityEnd();
}

src/linked_list.c

#include "linked_list.h"

#include <stdlib.h>


list_item **new_list(){
    list_item *list = malloc(sizeof(list_item));
    list->head = NULL;
    list->tail = NULL;
    list_item **res  = malloc(sizeof(list_item*));
    *res = list;
    return res;
}

bool is_list_empty(list_item **list){
    return !list || !(*list) || !(*list)->head;
}

bool push(list_item **list, ll_data_t item_data){
    if (!list){
        return false;
    }
    list_node *new_node = malloc(sizeof(list_node*));
    new_node->data = item_data;
    new_node->prev = NULL;
    new_node->next = NULL;
    if (is_list_empty(list)){
        (*list)->head = new_node;
        (*list)->tail = new_node;
    } else {
        new_node->prev = (*list)->tail;
        (*list)->tail->next = new_node;
        (*list)->tail = new_node;
    }
    return true;
}

ll_data_t pop(list_item **list){
    if(is_list_empty(list)){
        return 0;
    }
    list_node *rust_node = (*list)->tail;
    ll_data_t popped = rust_node->data;
    if((*list)->head == (*list)->tail){
        (*list)->tail = NULL;
        (*list)->head = NULL;
    } else {
        (*list)->tail = rust_node->prev;
        (*list)->tail->next =NULL;
    }
    free(rust_node);
    return popped;
}

ll_data_t shift(list_item **list){
    if(is_list_empty(list)){
        return 0;
    }
    list_node *head_node = (*list)->head;
    ll_data_t shifted = head_node->data;
    if((*list)->head == (*list)->tail){
        (*list)->head = NULL;
        (*list)->tail = NULL;
    } else {
        (*list)->head = head_node->next;
        (*list)->head->prev = NULL;
    }
    free(head_node);
    return shifted;
}

bool unshift(list_item **list, ll_data_t item_data){
    if (!list){
        return false;
    }
    list_node *new_node = malloc(sizeof(list_node*));
    new_node->data = item_data;
    new_node->next = NULL;
    new_node->prev = NULL;
    if (is_list_empty(list)){
        (*list)->head = new_node;
        (*list)->tail = new_node;
    } else {
        new_node->next = (*list)->head;
        (*list)->head->prev = new_node;
        (*list)->head = new_node;
    }
    return true;
}

void delete_list(list_item **list){
    while (!is_list_empty(list)){
        pop(list);
    }
    free(list);
}

src/linked_list.h

#ifndef LINKED_LIST_H
#define LINKED_LIST_H

#include <stdbool.h>
#include <stddef.h>

typedef int ll_data_t;

typedef struct list_node{
    ll_data_t data;
    struct list_node *prev;
    struct list_node *next;
} list_node;


typedef struct list_item{
    list_node *head;
    list_node *tail;
} list_item;

// constructs a new list of items
list_item **new_list(void);

// checks if the list is empty
bool is_list_empty(list_item **list);

// inserts item at back of list
bool push(list_item **list, ll_data_t item_data);

// removes item from back of list
ll_data_t pop(list_item **list);

// removes item from front of list
ll_data_t shift(list_item **list);

// inserts item at front of list
bool unshift(list_item **list, ll_data_t item_data);

// destroy the entire list
// list will be a dangling pointer after calling this method on it
void delete_list(list_item **list);

#endif

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?