Avatar of jsks

jsks's solution

to Linked List in the C Track

Published at Aug 21 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.c

#include <stdlib.h>

#include "linked_list.h"

struct list_item **new_list() {
    return calloc(1, sizeof(struct list_time *));
}

bool is_list_empty(struct list_item **list) {
    return !list || !(*list);
}

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

    free(list);
}

bool push(struct list_item **list, ll_data_t data) {
    if (!list)
        return false;

    struct list_item *p;
    if (!(p = malloc(sizeof(struct list_item))))
        return false;

    p->data = data;

    // If NULL, first node in empty list
    if (!(*list)) {
        *list = p->next = p->prev = p;
    } else {
        p->prev = *list;
        p->next = (*list)->next;

        (*list)->next->prev = p;
        (*list)->next = p;
    }

    return true;
}

ll_data_t pop(struct list_item **list) {
    struct list_item *p = (*list)->next;
    ll_data_t popped = p->data;

    // If pointers same, we've hit the end of the road
    if (p == p->prev)
        *list = NULL;
    else {
        p->next->prev = *list;
        (*list)->next = p->next;
    }

    free(p);

    return popped;
}

ll_data_t shift(struct list_item **list) {
    *list = (*list)->prev;
    return pop(list);
}

bool unshift(struct list_item **list, ll_data_t data) {
    if (!push(list, data))
        return false;

    *list = (*list)->next;
    return true;
}

src/linked_list.h

#ifndef LINKED_LIST_H
#define LINKED_LIST_H

#include <stdbool.h>

typedef int ll_data_t;

struct list_item {
    struct list_item *next;
    struct list_item *prev;
    ll_data_t data;
};

struct list_item **new_list(void);
bool is_list_empty(struct list_item **);
void delete_list(struct list_item **);

bool push(struct list_item **, int);
ll_data_t pop(struct list_item **);

ll_data_t shift(struct list_item **);
bool unshift(struct list_item **, int);

#endif

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?