Hey buds, In this article, I’m going to implement a linkedlist in java and compare our linked list on various performance benchmarks in comparison with the original collections linkedlist. Our custom linked list will not contain as many features as offered by the collections framework but it will surely contains all the basic features which are required to be a part of any list. So, let’s begin.
LinkedList Implementation
First of all we will create an interface List which will contain all the methods that a list must have in order to perform all its various functionalities. This list will be like a contract with its implementor that if it is implementing this interface than it is responsible for providing the necessary implementation for all these methods. Also, a List interface is used to provide the basic functionalities that every data structures must implement in order to be called as a list.
We want our list structures to add an item to it, remove an item from it, retrieve an item from it (GET) so for that I have created a contract (interface) that will force the implementation of these methods to the classes that are implementing it. Have a look at the List Interface below.
Interfaces are a really nice way to tell the implementor about the methods that are needed to be implemented in order to create an object with minimum functionality that is complete in itself. With a proper use of interface you can ease your development by a significant factor.
Next, we need a class which I have named CustomLinkedList which will implement the above List Interface and provide the implementation for those methods. By default, our class will have to provide the implementation for the methods provided above. Now, there are two approaches to provide the implementation for those methods:
Traditional Way – Simply start filling those methods with your code.
TDD Way – Test Driven Development which tells us to start by writing a test case and create your code backward.
I prefer the second option as it is often the best approach when it comes to writing a business logic for your class. I personally prefer this approach for writing business logic as it makes my code crisp and helps me divide it into different small modules which could be used multiple times, thus, saving bandwidth. TDD could be used to write entire application apart from business logic but then it’s not too fruitful.
I have embedded a complete Custom LinkedList class below implementation of all the methods. Just have a look at all the code and quickly move forward to TDD segment where we will be actually writing our code to make it a LinkedList.
TDD way
Normally, we would have to write lots of test cases to cover all the possible scenarios but I have kept it precise for you to understand and have fun with it and also appreciate the fact that it makes you so much more efficient. Once you grasp the concept of TDD then it becomes a playground for you. You automatically enjoy writing multiple test cases to make your application more robust and error free. The more scenarios you cover, more robust you make your application. We will give all the hard work to IDE for writing code for us and we will just write test cases.
Please take a look at below test cases that I have written to implement a linked list. These test cases are documentation in itself. It gives you a complete idea about a method and its functionality. Just by going over the test cases you can get a pretty decent idea of what that method does.
Benchmarks
Our custom linked list is going to be a little slow because of implementation logic followed. Have a look at below benchmarks:
Insertion
Insertion time for 5000 records using Custom Linked List Total Insertion time: 3157625 Insertion time for 5000 records using Original LinkedList Total Insertion time: 1034067
Deletion
Removal time Custom Linked List Total Removal time: 21554 Removal time Original LinkedList Total Removal time: 32844
Conclusion
TDD is the best way to program logic in your application. You don’t need any more reviews or approvals or testing because you know that your code is right. This is the kind of confident it develops in you. On top of that, it makes you a better programmer because you start to think in a different way which helps you to become more efficient.
Stay updated as I’m going to post some videos in which I will show you the approach on how to write test cases and leave all the difficult task of writing code and formatting to our smart IDE’s. Simply subscribe to our blogs and I will let you know once the videos are available.
Also, if you are more of a bookish guy then have a GO on the book mentioned below,
You might also want to read below articles,
- A beginners guide to understand collections
- Thinking in OOPS, How to think in terms of objects
- Lear real world object mapping with Shopping Cart Implementation in Java
If you have any doubt, simply comment below. Did you made any modification to your custom linked list to achieve higher performance then do let me know.
And as always
Be my aficionado 🙂