Implement doubly linked list data structure. This is quite big challenge, so we will split it into multiple multiple methods and properties that we will implement one my one.
We also want to handle various edge cases, because we are assuming that developer using our class many do certain
mistakes. That’s why each step has one or more tests associated with it. Tests are commented out default, so before
staring each step we will have to enable all tests related to given step by uncommenting it. To quickly uncomment the
test select all lines containing test method and press Cmd + / keys (Comment with line Comment action).
| Challenge | Solution |
DoublyLinkedList<E>()Create a class to represent a linked list. When created, a linked list should have no head node associated with it. The
DoublyLinkedList instance will have one property, head, which is a reference to the first node of the linked list. By
default head should be null.
Tests:
when list is created head node is nullExample:
val list = DoublyLinkedList<Any>()
list.head // null
insertFirst(data: E) methodCreates a Node from argument data and assigns the resulting node to the head property. Make sure to handle the case
in which the linked list already has a node assigned to the head property.
Tests:
append a node to the start of the listExample:
val list = DoublyLinkedList<String>()
list.insertFirst('Hi There') // List has one node
Example:
val list = DoublyLinkedList<String>()
list.insertFirst('Hi There') // List has one node
size propertyReturns the number of nodes in the linked list.
Tests:
return the number of items in the linked listExample:
val list = DoublyLinkedList<Char>()
list.insertFirst('a')
list.insertFirst('b')
list.insertFirst('c')
list.size() // 3
first: Node propertyReturns the first node of the linked list.
Tests:
return the first elementExample:
val list = DoublyLinkedList<Char>()
list.insertFirst('a')
list.insertFirst('b')
list.getFirst() // 'a'
last: Node propertyReturns the last node of the linked list
Tests:
return the last elementExample:
val list = DoublyLinkedList<Char>()
list.insertFirst('a')
list.insertFirst('b')
list.getLast() // 'a'
clear() methodEmpties the linked list of any nodes.
Tests:
empty out the listExample:
val list = DoublyLinkedList<Char>()
list.insertFirst('a')
list.insertFirst('b')
list.clear()
list.size() // 0
removeFirst() methodRemoves only the first node of the linked list. The list’s head should now be the second element.
Tests:
remove the first node when the list has a size of one,remove the first node when the list has a size of threeExample:
val list = DoublyLinkedList<Char>()
list.insertFirst('a')
list.insertFirst('b')
list.removeFirst()
list.getFirst() // 'a'
removeLast() methodRemoves the last node of the chain.
Tests:
remove the last node when list is empty,remove the last node when list is length 1,remove the last node when list is length 2,remove the last node when list is length 3Example:
val list = DoublyLinkedList<Char>()
list.insertFirst('a')
list.insertFirst('b')
list.removeLast()
list.size() // 1
list.getLast() // of 'b'
insertLast(data: E) methodInserts a node with given data at the end of the chain.
Tests:
add to the end of the listExample:
val list = DoublyLinkedList<Char>()
list.insertFirst('a')
list.insertFirst('b')
list.insertLast('c')
list.getLast() // 'C'
getAt(index: Int) methodReturns the node at the given index.
Tests:
return the node at given indexExample:
val list = DoublyLinkedList<Char>()
list.insertFirst('a')
list.insertFirst('b')
list.insertFirst('c')
list.getAt(1) // 'b'
setAt() methodSet the value at given index.
Tests:
set node data at index 0set node data at the index 1set node data at the index 2set node data at non existing indexExample:
val list = DoublyLinkedList<Char>()
list.insertLast("a")
list.insertLast("b")
list.insertLast("c")
list.setAt("new", 1)
list.getAt(0) // "a"
list.getAt(1) // "new"
list.getAt(2) // "c"
removeAt(index: Int) methodRemoves node at the given index.
Tests:
remove from empty listremove with index out of boundsremove the first noderemove the node at given indexremove the last nodeExample:
val list = DoublyLinkedList<Char>()
list.insertFirst('a')
list.insertFirst('b')
list.insertFirst('c')
list.removeAt(1)
list.getAt(1) // 'a'
insertAt(data: E, index: Int) methodCreate an insert a node at given index. If index is out of bounds, add the node to the end of the list.
Tests:
insert a new node with data at the 0 index 0 when the list is emptyinsert a new node with data at index 0 when the list has elementsinserts a new node with data at a middle indexinsert a new node with data at a last indexinsert a new node when index is out of boundsExample:
val list = DoublyLinkedList<Char>()
list.insertFirst('a')
list.insertFirst('b')
list.insertFirst('c')
list.insertAt('H', 1)
list.getAt(1) // 'H'
Iterator interfaceAllows to iterate over list of items using t Kotlin
Iterable and
Iterator interfaces. This
allows to use many Kotlin extensions for Iterable interface such as forEach, filter, sumBy, map etc.
Tests:
sum all the nodesExample 1:
val list = DoublyLinkedList<Int>()
list.insertLast(1)
list.insertLast(2)
list.insertLast(3)
list.insertLast(4)
list.forEach { print(node) } // 1234
Example 2:
val list = DoublyLinkedList()
list.insertLast(1)
list.insertLast(2)
list.insertLast(3)
list.insertLast(4)
list.sumBy { it.data } // 10
Implement operator overloading to easily add two lists lists.
Tests
add two empty lists, add two listsval list1 = DoublyLinkedList<Int>()
list1.insertLast(1)
list1.insertLast(2)
val list2 = DoublyLinkedList<Int>()
list2.insertLast(3)
list2.insertLast(4)
list2.insertLast(5)
list.size shouldBeEqualTo 5
list.getAt(0)?.data shouldBeEqualTo 1
list.getAt(1)?.data shouldBeEqualTo 2
list.getAt(2)?.data shouldBeEqualTo 3
list.getAt(3)?.data shouldBeEqualTo 4
list.getAt(4)?.data shouldBeEqualTo 5