Code Katas: Linked Lists

I explored in a previous post the idea of a coding kata. I explained that I thought that data structures, design patterns, and fundamental algorithms are ideal for such practice.

I think a good way to practice them is to start with the tests, and practice the kata from there. In this light, last week I put forward the tests for the Stack kata.

This week it’s Linked Lists.

Background

A linked list is a data structure is a linear collection of data elements, called nodes. In it’s most basic form each node contains two pieces of information:

  • The data itself
  • A pointer that points to the next node

I came up with 20 tests (22 assertions) to implement this:

  1. New linked list init
  2. New linked list, next is null
  3. New Linked list, getLength is 0
  4. Add value once to list, getLength is 1
  5. Add value once, searchValueAt(0) returns value
  6. Add value once, searchValueAt(1) returns null
  7. Add two values, getLength is 2
  8. Add two values, searchValueAt(1) returns second value
  9. Add two values, searchValueAt(0) returns first value
  10. Remove node on empty list, length is 0
  11. Add value, remove node, length is 0
  12. Add value, remove node, list is empty
  13. Add value, remove node, add value, first is second value
  14. Add two values, remove second, length is 1
  15. Add two values, remove at third position, length is 2
  16. Add two values, remove second, first is value and next is empty
  17. Add two values, remove first, length is 1
  18. Add two values, remove first, first is second value
  19. Add three values, remove second, length is 2
  20. Add three values, remove second, first is value and second is third value

Here’s my implementation, but really I’m more interested in yours. Post a link to your repo below!

Image credit I explored in a previous post the idea of a coding kata. I explained that I thought that data structures, design patterns, and fundamental algorithms are ideal for such practice.

I think a good way to practice them is to start with the tests, and practice the kata from there. In this light, last week I put forward the tests for the Stack kata.

This week it’s Linked Lists.

Background

A linked list is a data structure is a linear collection of data elements, called nodes. In it’s most basic form each node contains two pieces of information:

  • The data itself
  • A pointer that points to the next node

I came up with 20 tests (22 assertions) to implement this:

  1. New linked list init
  2. New linked list, next is null
  3. New Linked list, getLength is 0
  4. Add value once to list, getLength is 1
  5. Add value once, searchValueAt(0) returns value
  6. Add value once, searchValueAt(1) returns null
  7. Add two values, getLength is 2
  8. Add two values, searchValueAt(1) returns second value
  9. Add two values, searchValueAt(0) returns first value
  10. Remove node on empty list, length is 0
  11. Add value, remove node, length is 0
  12. Add value, remove node, list is empty
  13. Add value, remove node, add value, first is second value
  14. Add two values, remove second, length is 1
  15. Add two values, remove at third position, length is 2
  16. Add two values, remove second, first is value and next is empty
  17. Add two values, remove first, length is 1
  18. Add two values, remove first, first is second value
  19. Add three values, remove second, length is 2
  20. Add three values, remove second, first is value and second is third value

Here’s my implementation.