How do I add an item to a linked list?
Linked List is a simple data structure. Implementing it from scratch helps to understand its properties. Well implement Linked List add, size, and print its contents. Show Linked List constructionTo construct Linked List well need two things. One is an internal representation of Linked List Node, the other is the reference to the first element of the list the head. This can be represented like here: package com.farenda.tutorials.algorithms.lists; public class LinkedListPrint content of Linked ListTo help ourselves to verify results of our work well start with implementation of a helper method that prints the contents of a Linked List. As many algorithms on Linked Lists this one works in linear time O(N), because it has to go through the whole list: Add element to the end of Linked ListThe algorithm has to handle two cases:
Again, the algorithm has linear time complexity O(N), because it has to traverse whole list to add element at the end. Count number of elements in Linked ListAnother useful method to have is list.size(), which will return the number of elements in Linked List. It works almost exactly the same as addition, therefore its running time is proportional to the size of the list, so its O(N): public int size() { int count = 0; NodeUnit testsLets implement a few JUnit tests that will help us verify correctness of the algorithms: package com.farenda.tutorials.algorithms.lists; import org.junit.Test; import static org.junit.Assert.*; public class LinkedListTest { private LinkedListNow, when we run the above tests they will output something similar to (order may be different, due to the different execution order): [1] [1,42] [1,42,2,3] []References:
Share with the World! |