sardtok / datastructures Goto Github PK

Add a linked list implementation the Scala programming language.

The list should be generic.
The list should be immutable.
The list should implement typical functions like map, for each, filter, fold, etc.

Tests similar to the Java version should be added.

The linked list implementations should allow removing the first element or last element, and insertion at the beginning of the list as well as the end of the list.

For Java, the list should implement the double ended queue interface: Deque.

Unit tests are needed.
There are obvious bugs in the iterator with regards to indices.

Tests that need adding:

• Add:
  • Null cannot be added
  • Should return true
  • Size should change
  • List should contain added element
  • Element should be accessible at the index: (size - 1)
• Get:
  • Should retrieve the correct elements
• Contains:
  • Should return true for elements that are in the list
  • Should return false for elements that are not in the list
• Remove by index:
  • Should return the same element as get on the same index
  • Should no longer contain element after removal (if it is the only instance)
  • Size should change
• Remove by object reference:
  • Should return true if the element exists in the list
  • Size should change
  • Should no longer contain element (if it is the only instance)
• Iterator:
  • Should iterate properly from start to finish
  • Should iterate properly backwards
  • Should yield the correct indices for next and previous elements
  • Should allow removing elements
  • Should allow exchanging elements

All methods should be tested, but these should make for a decent amount of early tests. More tests can be added when a method is to be implemented.

One way to perform the tests, is to compare it to the reference implementation, java.util.LinkedList, as it should perform the same actions.

Add a linked list implementation the C programming language.

The list should be general, using void pointers.
The list should support at least some more advanced functions than simply, add and remove. Possible additions: filter, remove all, retain all.

Tests similar to the Java version should be added.

LinkedList.remove(int) throws a NoSuchElementException instead of an IndexOutOfBoundsException when the index is equal to size.

Need to implement testing for correct exceptions.
Need to explicitly check indices in remove, instead of relying on the iterator to throw the right exception.

Add a linked list implementation JavaScript/ECMAScript.

Consider writing an immutable list type.
Should be JSON serializable to a standard JSON list.
Should work similar to a standard JS list.
Should support Harmony iterators (ECMAScript 6 iterators that allow for-of loops).

Tests similar to the Java version should be added.

The only part of the java.util.List interface not implemented by the current implementation is sub-lists.

Although sub-lists may be useful for simplifying or speeding up certain operations (deleting a large portion of the list), there is some added overhead due to the effects on the super-list.

The list iterator in the LinkedList uses zero as the lowest index if created with an index in the first half of the list. However, if the constructor is called with an index in the last half of the list, one is used as the lowest index (i.e. the size is inclusive, instead of exclusive).