Implementing a Singly or Doubly Linked List in Java (A LeetCode Question)

Task description:

Design your implementation of the linked list. You can choose to use a singly or doubly linked list.

A node in a singly linked list should have two attributes: val and next. val is the value of the current node, and next is a pointer/reference to the next node.

If you want to use the doubly linked list, you will need one more attribute prev to indicate the previous node in the linked list. Assume all nodes in the linked list are 0-indexed.

Implement the MyLinkedList class:

https://gist.github.com/RakhmedovRS/70950a8b5d8c6669cdd270d3ef7737e1

• MyLinkedList() Initializes the MyLinkedList object.
• int get(int index) Get the value of the indexth node in the linked list. If the index is invalid, return -1.
• void addAtHead(int val) Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list.
• void addAtTail(int val) Append a node of value val as the last element of the linked list.
• void addAtIndex(int index, int val) Add a node of value val before the indexth node in the linked list. If index equals the length of the linked list, the node will be appended to the end of the linked list. If index is greater than the length, the node will not be inserted.
• void deleteAtIndex(int index) Delete the indexth node in the linked list, if the index is valid.

Example 1:

Input
["MyLinkedList", "addAtHead", "addAtTail", "addAtIndex", "get", "deleteAtIndex", "get"]
[[], [1], [3], [1, 2], [1], [1], [1]]
Output
[null, null, null, null, 2, null, 3]
Explanation
MyLinkedList myLinkedList = new MyLinkedList();
myLinkedList.addAtHead(1);
myLinkedList.addAtTail(3);
myLinkedList.addAtIndex(1, 2);    // linked list becomes 1->2->3
myLinkedList.get(1);              // return 2
myLinkedList.deleteAtIndex(1);    // now the linked list is 1->3
myLinkedList.get(1);              // return 3

Constraints:

• 0 <= index, val <= 1000
• Please do not use the built-in LinkedList library.
• At most 2000 calls will be made to get, addAtHead, addAtTail, addAtIndex and deleteAtIndex.

My thoughts:

I personally love tasks like this. It can be solved in many different ways that if we are to describe them you’ll be bored and tired of reading that amount of information. This task may help you to build or improve your skill of dividing tasks into smaller pieces. Again it’s an extremely important skill if you want to become a great software engineer. If you already have got experience in algorithms and data structures you could some something like this.

https://gist.github.com/RakhmedovRS/beb76bad4c696c6ca962a46e5631d545

It’s perfectly fine to solve the problem this way but it only works when you already know how LinkedList works and you’re able to implement it from the scratch. While approach above can save you time. I suggest diving deeper and implementing our own version of LinkedList. I’m pretty sure many of you know how it works but when I ask you to implement is some of you may struggle.

I think after you read or learn something you should implement what you just learned. It’ll help you to understand how this data structure works and where it can be used. Knowledge you got will be memorized better.

Reasoning:

As I said this task is a perfect example of where we may split a big task into smaller ones. So let’s try to understand how to do it.

Seem like we need to implement at least 5 different methods. It’s a great starting point. While having bigger picture in your head we could focus on specific subproblem which every method must solve. Let’s solve smaller problems one by one.

According to the description method int get(int index)can receive index of element and return the element at this index if we have it in our list. Sounds pretty straightforward. We have list with elements, let’s iterate though it and keep track current index and index we’re provided. If they’re equal we found the element and can return. In all other cases we return -1. Pay attention to line 11. We use head as it stores the link to the head of the list. Please keep it mind, we’ll get back to it.

Example: we have list 1 -> 2 -> 3 -> 4 ->5

1 has index 0, 2 has index 1 and so on. If we’re given index 3 we must return 4

https://gist.github.com/RakhmedovRS/ca3d76ae29d1210d6eb312f9350385d5

The next method in our list is void addAtHead(int val) it must insert value in the front of our list. This one is a bit tricky. We have head which stores the link to the head so we want to push the next element and insert provided value right after the head. The first thing we do is create the new Link which will be storing provided value(scheme below). At the same time, we need to update the relations between existing links and the new one. Instead of using words let’s look at some pictures I hope I’ll help you to understand the concept

We also have a variable size which is here to store the number of elements in our list.

https://gist.github.com/RakhmedovRS/f18182ba692a76502f4444bf58410af6

https://gist.github.com/RakhmedovRS/b84d3c5758832540450b394dd69d85d2

The next method is void addAtTail(int val) it does almost the same thing as the previous one, the only difference is we insert our value before the tail of our list.

https://gist.github.com/RakhmedovRS/47272129eea9dbc18b78f1591e79d3cd

The next method is void addAtIndex(int index, int val) it must insert a value in LinkedList at a particular index which is provided as a parameter. The first node after head has index 0, the next to it has index 1 and so on.

Our goal is to iterate to target index and insert value at that index. Let’s insert value 5 at index 1.

https://gist.github.com/RakhmedovRS/c032fe01f6ac4679295c1ef1ec5c1f31

Our last method to implement is void deleteAtIndex(int index) . It does almost the same thing as an insert at index, except one thing, this time we delete Link. This article is getting too big so I provide some pictures and code to make it easier to understand. Let’s delete node at index 3.

https://gist.github.com/RakhmedovRS/4b67829babc66f0a3d1845d6017d48dd

https://gist.github.com/RakhmedovRS/db7a74650045b6fe108b159525b7a579

The code above gives us the following results

Also Published here