## 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:**

```javascript
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

 ![Initial state of MyLinkedList](https://cdn.hackernoon.com/images/e2lhyGaGa6ZVTWmBikAWsw2Fj0O2-jw93nab.png)

 ![We created new Link with value 5](https://miro.medium.com/max/1400/1\*mnzLGcVxTi22Tb2tx-Trpg.png)

 ![State of MyLinkedList once we updated all links](https://miro.medium.com/max/1400/1\*RdgUZ9F9XnKZy-ELDKfmLg.png)

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>

 ![Initial state of MyLinkedList](https://miro.medium.com/max/1400/1\*rdjprjw3LC6hsUvFT7duSA.png)

 ![We created a new Link with value 7](https://miro.medium.com/max/1400/1\*4FXUbh1DCIHawzfkf85Xsw.png)

 ![State of MyLinkedList once we updated all links](https://miro.medium.com/max/1400/1\*rBXzqQdwfE_Hq10TEBrakg.png)


---

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.

 ![Values and indices of nodes in MyLinkedList](https://miro.medium.com/max/1400/1\*egdpsffZdY12hk0FtHaFkA.png)

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

 ![We created a new Link with value 5](https://miro.medium.com/max/1400/1\*EACkHJbc9u_NWExSWDGyZg.png)

 ![State of MyLinkedList once we updated all links](https://miro.medium.com/max/1400/1\*o0BUwEhftrwQaa_ZJ28hTg.png)

<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.

\
 ![Initial state of MyLinkedList](https://miro.medium.com/max/1400/1\*o0BUwEhftrwQaa_ZJ28hTg.png)

 ![State of MyLinkedList once we updated all links](https://miro.medium.com/max/1400/1\*-X8CDyMgai1tQmvSYqbl8Q.png)

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


---

\
<https://gist.github.com/RakhmedovRS/db7a74650045b6fe108b159525b7a579>

\
The code above gives us the following results

 ![](https://miro.medium.com/max/1270/1\*IsA5UXPz7TL8TnCUqJ-0bQ.png)

*Also Published [here](https://levelup.gitconnected.com/java-algorithms-design-linked-list-leetcode-ecbd7edbb022)*

Target

2022 - HackerNoon Contributor of the Year - Algorithms

2022 - HackerNoon Contributor of the Year - Coding

2022 - HackerNoon Contributor of the Year - Java

Nominated for 2022 - HackerNoon Contributor of the Year - Algorithms

Nominated for 2022 - HackerNoon Contributor of the Year - Java

Nominated for 2022 - HackerNoon Contributor of the Year - Coding

Too Long; Didn't Read

Cassandra Forward a free Cassandra-focused community event

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

Too Long; Didn't Read

Company Mentioned

@rakhmedovrs

RELATED STORIES