Avatar of mstange22

mstange22's solution

to Linked List in the C Track

Published at Aug 07 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.h

#ifndef LINKED_LIST_H
#define LINKED_LIST_H
#include <stddef.h>
#include <stdbool.h>

typedef int ll_data_t;

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

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

list_item **new_list();
bool is_list_empty(list_item** list);
bool push(list_item** list, ll_data_t data);
size_t pop(list_item **list);
bool unshift(list_item** list, ll_data_t data);
size_t shift(list_item **list);
void delete_list(list_item** list);

#endif

src/linked_list.c

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

list_item **new_list() {
  list_item *list = malloc(sizeof(list_item));
  if (!list) return NULL;

  list->head = NULL;
  list->tail = NULL;

  list_item **res = malloc(sizeof(list_item*));
  if (!res) return NULL;

  *res = list;
  return res;
}

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

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

  list_node *new_item = (list_node*)malloc(sizeof(list_node));
  if (!new_item) return false;

  new_item->data = data;
  new_item->next = NULL;
  new_item->prev = NULL;

  // pushing to empty list
  if (is_list_empty(list)) {
    (*list)->head = new_item;
    (*list)->tail = new_item;
  } else if ((*list)->head == (*list)->tail) { // one element
    new_item->prev = (*list)->head;
    (*list)->head->next = new_item;
    (*list)->tail = new_item;
  } else {
    new_item->prev = (*list)->tail;
    (*list)->tail->next = new_item;
    (*list)->tail = (*list)->tail->next;
  }
  return true;
}

size_t pop(list_item **list) {
  if (is_list_empty(list)) return 0;

  size_t res = (*list)->tail->data;

  // if only one node
  if ((*list)->head == (*list)->tail) {
    free((*list)->tail);
    (*list)->head = NULL;
    (*list)->tail = NULL; 
  } else {
    (*list)->tail->prev->next = NULL;
    list_node *temp = (*list)->tail;
    (*list)->tail = (*list)->tail->prev;
    free(temp);
  }
  return res;
}

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

  list_node *new_item = (list_node*)malloc(sizeof(list_node));
  if (!new_item) return false;

  new_item->data = data;
  new_item->next = NULL;
  new_item->prev = NULL;

  // unshifting to empty list
  if (is_list_empty(list)) {
    (*list)->head = new_item;
    (*list)->tail = new_item;
  } else if ((*list)->head == (*list)->tail) { // one element
    new_item->next = (*list)->tail;
    (*list)->tail->prev = new_item;
    (*list)->head = new_item;
  } else {
    new_item->next = (*list)->head;
    (*list)->head->prev = new_item;
    (*list)->head = (*list)->head->prev;
  }
  return true;
}

size_t shift(list_item **list) {
  if (is_list_empty(list)) return 0;
  
  size_t res = (*list)->head->data;

  // if only one node
  if ((*list)->head == (*list)->tail) {
    free((*list)->head);
    (*list)->head = NULL;
    (*list)->tail = NULL; 
  } else {
    (*list)->head->next->prev = NULL;
    list_node *temp = (*list)->head;
    (*list)->head = (*list)->head->next;
    free(temp);
  }
  return res;
}

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

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?