Singly Linked List implementation

[dgraciac]

First step

Search, read and understand information about lists, linked lists and singly linked lists, and how they are implemented.

Second step

You have to share a code snippet in markdown with an interface proposal for this data structure. Below you can find an interface example of an hypothetical data structure:

class MyDataStructure<E> {

    fun add(element: E) {
        TODO("Not yet implemented")
    }

    fun get(index: Int): E {
        TODO("Not yet implemented")
    }
}

Third step

After @code-sherpas/kollections-maintainers approve your interface proposal, open a pull request with the data structure implementation and wait for comments.

Minimum acceptance criteria

• The implementation must be well documented with proper Javadoc at Class and function levels.
• The implementation must be tested with automatic tests that cover all relevant cases and situations.
• The implementation must be generic.
• The implementation must have the expected time complexity according to the Computer Science. Here you can find a very helpful cheatsheet.

Related resources:

• https://www.youtube.com/watch?v=v4cd1O4zkGw&ab_channel=HackerRank
• https://www.youtube.com/watch?v=njTh_OwMljA&ab_channel=HackerRank
• https://en.wikipedia.org/wiki/List_(abstract_data_type)
• https://en.wikipedia.org/wiki/Linked_list#Singly_linked_list
• https://www.bigocheatsheet.com/

[ashikka]

@dgraciac Here is the interface proposal for this data structure. Let me know if you require any changes.

package main
class SinglyLinkedList<E> {

    // Insert element at the beginning of the list
    fun insertAtBeginning(element: E){
        TODO()
    }

    // Insert element after a specified node
    fun insertAfter(previousNode: E, element: E){
        TODO()
    }

    // Insert element at the end of the list
    fun insertAtEnd(element: E){
        TODO()
    }

    // Delete a node of a specified position
    fun deleteNode(position: E){
        TODO()
    }
}

[dgraciac]

Positions are integers

 fun deleteNode(position: Int){
        TODO()
    }

[dgraciac]

Passing a node is not needed:

    // Insert element after the first ocurrence of specified element
    fun insertAfter(element: E){
        TODO()
    }

[dgraciac]

After this interface changes, you can go with the implementation.

[dgraciac]

Consider add this operations in this PR. But up to you.

fun get(index: Int): E

fun isEmpty(): Boolean

fun head(): E

[ashikka]

Is this alright @dgraciac?

package main
class SinglyLinkedList<E> {

    // Insert element at the beginning of the list
    fun insertAtBeginning(element:E) {
        TODO()
    }

    // Insert element at the end of the list
    fun insertAtEnd(element:E) {
        TODO()
    }

    // Delete a node of a specified position
    fun deleteNode(position:Integer) {
        TODO()
    }

    // Get element at a specified position
    fun get(index:Integer):E {
        TODO()
    }

    // Check is list is empty
    fun isEmpty(): Boolean{
        TODO()
    }

    // Find the element at the head of the list
    fun head():E{
        TODO()
    }
}

[dgraciac]

Please remove this operation because I am not sure it is worth it:

// Insert element after a specified node
    fun insertAfter(element:E) {
        TODO()
    }

You can start with the implementation.