Linked List is a very commonly used linear data structure which consists of group of nodes in a sequence. Each node holds its own data and the address of the next node hence forming a chain like structure.

Linked Lists are used to create trees and graphs.

• Linkedlist is dynamic in nature which means it can expand in constant time. It does not have to create a new array as dynamic array does.
• Insertion and deletion operations can be easily implemented.
• Stacks and queues can be easily executed.
• Linked List reduces the access time.

• The memory is wasted as pointers require extra memory for storage.
• No element can be accessed randomly; it has to access each node sequentially.
• Reverse Traversing is difficult in linked list.

### Where to use Linked List

• Linked lists are used to implement stacks, queues, graphs, etc.
• Linked lists let you insert elements at the beginning and end of the list.
• In Linked Lists we don’t need to know the size in advance.

### When to use Linked List

• When you insert and delete elements often from a list.

There are 3 different implementations of Linked List available, they are:

Singly linked lists contain nodes which have a data part as well as an address part i.e. `next`, which points to the next node in the sequence of nodes.

The operations we can perform on singly linked lists are insertiondeletion and traversal.

```@ToString
@NoArgsConstructor
@AllArgsConstructor
@Data
public class Customer {

private String firstName;
private String lastName;
private String email;
}
```

```@ToString
@Data
public class SingleNode {

private Customer data;
private SingleNode     next;

public SingleNode(Customer data) {
this(data, null);
}

public SingleNode(Customer data, SingleNode next) {
this.data = data;
this.next = next;
}

}
```

```@NoArgsConstructor
@Data

int                size = 0;

private SingleNode tail;

}

/**
* add to end of list<br>
* 2. If the Linked List is not empty then we find the last node, and make it' next to the new Node, hence making
* the new node the last Node.
*
* Time complexity of append is O(n) where n is the number of nodes in the linked list. Since there is a loop from
* head to end, the function does O(n) work. This method can also be optimized to work in O(1) by keeping an extra
* pointer to the tail of the linked list.
*/
public void append(SingleNode node) {
if (node == null) {
return;
}
this.tail = node;
} else {
this.tail.setNext(node);
this.tail = node;
}
size++;
}

/**
* append to front of list<br>
* 1. The first Node is the Head for any Linked List.<br>
* 2. When a new Linked List is instantiated, it just has the Head, which is Null.<br>
* 3. Else, the Head holds the pointer to the first Node of the List.<br>
* 4. When we want to add any Node at the front, we must make the head point to it.<br>
* 5. And the Next pointer of the newly added Node, must point to the previous Head, whether it be NULL(in case of
* new List) or the pointer to the first Node of the List.<br>
* 6. The previous Head Node is now the second Node of Linked List, because the new Node is added at the front.<br>
*/
public void prepend(SingleNode node) {
if (node == null) {
return;
}
} else {
}
size++;
}

/**
* add at position of list
*/
public void add(int index, SingleNode node) {
if (node == null) {
return;
}

int count = 0;

/*
*/
node.setNext(currentNode);

} else if (this.tail.equals(currentNode)) {

this.tail.setNext(node);
this.tail = node;

}

SingleNode previous = null;

while (currentNode.getNext() != null) {

if (index == count) {
break;
}

previous = currentNode;
currentNode = currentNode.getNext();

count++;

}

node.setNext(currentNode);
previous.setNext(node);

size++;
}

/**
* is empty?
*/
public boolean isEmpty() {
return size <= 0 || this.head == null;
}

/**
* exist? search by email
*/
public boolean existByEmail(String email) {
if (email == null || email.length() <= 0) {
return false;
}
return false;
} else {

/**
* when email is found, break out of while loop
*/
while (!currentNode.getData().getEmail().equalsIgnoreCase(email.toLowerCase())) {

/**
*/
if (currentNode.getNext() == null) {
return false;
}

currentNode = currentNode.getNext();
}
return true;
}

}

/**
* get node on index
*/
public SingleNode get(int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("index out of bounds");
}

if (index == 0) {

} else if (index == (size - 1)) {

return this.tail;

} else {

int count = 0;

while (currentNode.getNext() != null) {
currentNode = currentNode.getNext();

count++;

if (index == count) {
break;
}

}
return currentNode;
}

}

/**
* remove node base on index<br>
* 1. If the Node to be deleted is the first node, then simply set the Next pointer of the Head to point to the next
* element from the Node to be deleted.<br>
* 2. If the Node is in the middle somewhere, then find the Node before it, and make the Node before it point to the
* Node next to it.<br>
*/
public void removeAt(int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("index out of bounds");
}

if (index==0) {

return;

}

int count = 1;

SingleNode next = null;

while (count < index) {

previous = currentNode;
currentNode = currentNode.getNext();
next = currentNode.getNext();

count++;

}

if (currentNode.equals(this.tail)) {

this.tail = previous;
this.tail.setNext(null);

} else {
// drop currentNode
previous.setNext(next);
}

}

/**
* remove all<br>
*/

public void removeAll() {
this.tail = null;
}

/**
* print out list
*/

public void printList() {
System.out.println("list is empty");
}

int count = 0;
while (node != null) {
System.out.println("index: " + count);
System.out.println("data: " + node.getData().toString());
node = node.getNext();

if (node == null) {
System.out.println("tail: " + tail.getData().toString());
System.out.println("end of list\n");
}

System.out.println("\n");

count++;
}

}
}
```

In a doubly linked list, each node contains a data part and two addresses, one for the previous node and one for the next node.

```@AllArgsConstructor
@ToString
@Data
public class DoubleNode {

private DoubleNode prev;
private Customer   data;
private DoubleNode next;

public DoubleNode(Customer data) {
this(null, data, null);
}
}```
```@NoArgsConstructor
@Data

int                size = 0;

private DoubleNode tail;

}

/**
* add to end of list<br>
* 2. If the Linked List is not empty then we find the last node, and make it' next to the new Node, hence making
* the new node the last Node.
*/
public void append(DoubleNode node) {
if (node == null) {
return;
}
this.tail = node;
} else {
while (currentNode.getNext() != null) {
currentNode = currentNode.getNext();
}
// order doesn't matter, as long as the last operation is tail=node
this.tail.setNext(node);
node.setPrev(this.tail);
this.tail = node;

}
size++;
}

/**
* append to front of list<br>
* 1. The first Node is the Head for any Linked List.<br>
* 2. When a new Linked List is instantiated, it just has the Head, which is Null.<br>
* 3. Else, the Head holds the pointer to the first Node of the List.<br>
* 4. When we want to add any Node at the front, we must make the head point to it.<br>
* 5. And the Next pointer of the newly added Node, must point to the previous Head, whether it be NULL(in case of
* new List) or the pointer to the first Node of the List.<br>
* 6. The previous Head Node is now the second Node of Linked List, because the new Node is added at the front.<br>
*/
public void prepend(DoubleNode node) {
if (node == null) {
return;
}
} else {

// order doesn't matter, as long as the last operation is head=node
}
size++;
}

/**
* add at position of list
*/
public void add(int index, DoubleNode node) {
if (node == null) {
return;
}

int count = 0;

if (index == 0) {

node.setNext(currentNode);

} else if (index == (size - 1)) {

this.tail.setNext(node);
this.tail = node;

} else {

DoubleNode previous = null;

while (currentNode.getNext() != null) {

if (index == count) {
break;
}

previous = currentNode;
currentNode = currentNode.getNext();

count++;

}

node.setNext(currentNode);
previous.setNext(node);

}

size++;
}

/**
* is empty?
*/
public boolean isEmpty() {
return size <= 0 || this.head == null;
}

/**
* exist? search by email
*/
public boolean existByEmail(String email) {
if (email == null || email.length() <= 0) {
return false;
}
return false;
} else {

/**
* when email is found, break out of while loop
*/
while (!currentNode.getData().getEmail().equalsIgnoreCase(email.toLowerCase())) {

/**
*/
if (currentNode.getNext() == null) {
return false;
}

currentNode = currentNode.getNext();
}
return true;
}

}

/**
* get node on index
*/
public DoubleNode get(int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("index out of bounds");
}
if (index == 0) {
}

if (index == 0) {

} else if (index == (size - 1)) {

return this.tail;

} else {

int count = 0;

while (currentNode.getNext() != null) {
currentNode = currentNode.getNext();

count++;

if (index == count) {
break;
}

}
return currentNode;
}

}

/**
* remove node base on index<br>
* 1. If the Node to be deleted is the first node, then simply set the Next pointer of the Head to point to the next
* element from the Node to be deleted.<br>
* 2. If the Node is in the middle somewhere, then find the Node before it, and make the Node before it point to the
* Node next to it.<br>
*/
public void remove(int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("index out of bounds");
}

int count = 0;

if (index == 0) {

} else if (index == (size - 1)) {

this.tail = this.tail.getPrev();
this.tail.setNext(null);

} else {

DoubleNode previous = null;
DoubleNode next = null;

while (currentNode.getNext() != null) {

if (index == count) {
break;
}

previous = currentNode;
currentNode = currentNode.getNext();
next = currentNode.getNext();

count++;

}

previous.setNext(next);
next.setPrev(previous);

}

}

/**
* remove all<br>
*/

public void removeAll() {
this.tail = null;
}

/**
* print out list
*/

public void printList() {
System.out.println("list is empty");
}

int count = 0;
while (node != null) {
System.out.println("index: " + count);
System.out.println("prev: " + ((node.getPrev() != null) ? node.getPrev().getData().toString() : ""));
System.out.println("current: " + node.getData().toString());
System.out.println("next: " + ((node.getNext() != null) ? node.getNext().getData().toString() : ""));
node = node.getNext();

if (node == null) {
System.out.println("tail: " + tail.getData().toString());
System.out.println("end of list\n");
}

System.out.println("\n");

count++;
}

}
}```

In circular linked list the last node of the list holds the address of the first node hence forming a circular chain.

### Time Complexity

Data Structure Time Complexity Space Complexity
Average Worst Worst
Access Search Insertion Deletion Access Search Insertion Deletion
Singly-Linked List  `Θ(n)` `Θ(n)` `Θ(1)` `Θ(1)` `O(n)` `O(n)` `O(1)` `O(1)` `O(n)`
Doubly-Linked List  `Θ(n)` `Θ(n)` `Θ(1)` `Θ(1)` `O(n)` `O(n)` `O(1)` `O(1)` `O(n)`
• add() – appends an element to the end of the list. So it only updates the tail node, therefore O(1) constant-time complexity.
• add(index, element) – in average runs in O(n) time
• get() – searching for an element takes O(n) time
• remove(element) – to remove an element, only pointers have to be updated. This operation is O(1).
• remove(index) – to remove an element by index, we first need to find it, therefor the overall complexity is O(n)
• contains() – also has O(n) time complexity

Source code on Github