LISTS
Lists are a fundamental data structure used in computer science and programming. They are a collection of elements or items stored in a linear sequence, with each element pointing to the next one in the sequence. Lists can be used to store any type of data, including integers, floating-point numbers, characters, strings, and even more complex data structures.
Lists can be implemented using arrays or linked lists. In an array implementation, the elements are stored in contiguous memory locations, and the indices are used to access them. In a linked list implementation, each element is stored in a node, which contains a reference to the next node in the list.
Lists can be used to implement many other data structures, such as stacks, queues, and trees. They are also commonly used to represent sequences of data in algorithms, such as sorting algorithms and search algorithms.
SINGLY LINKED LISTS
A singly linked list is a data structure that consists of a sequence of nodes, where each node contains an element of data and a reference (or pointer) to the next node in the sequence. The first node in the sequence is called the head, and the last node is called the tail. In a singly linked list, traversal is only allowed in one direction, from the head to the tail.
Here's an example implementation of a singly linked list in Java:
public class SinglyLinkedList<T> {
private Node<T> head;
private Node<T> tail;
private int size;
private static class Node<T> {
T data;
Node<T> next;
Node(T data) {
this.data = data;
}
}
public SinglyLinkedList() {
head = null;
tail = null;
size = 0;
}
public void addFirst(T data) {
Node<T> node = new Node<>(data);
if (head == null) {
head = node;
tail = node;
} else {
node.next = head;
head = node;
}
size++;
}
public void addLast(T data) {
Node<T> node = new Node<>(data);
if (tail == null) {
head = node;
tail = node;
} else {
tail.next = node;
tail = node;
}
size++;
}
public T removeFirst() {
if (head == null) {
return null;
}
T data = head.data;
if (head == tail) {
head = null;
tail = null;
} else {
head = head.next;
}
size--;
return data;
}
public T removeLast() {
if (tail == null) {
return null;
}
T data = tail.data;
if (head == tail) {
head = null;
tail = null;
} else {
Node<T> current = head;
while (current.next != tail) {
current =
current.next;
}
current.next = null;
tail = current;
}
size--;
return data;
}
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
public void clear() {
head = null;
tail = null;
size = 0;
}
public void print() {
Node<T> current = head;
while (current != null) {
System.out.print(current.data + "
");
current = current.next;
}
System.out.println();
}
}
In this implementation, the SinglyLinkedList class has a private inner class Node that defines a node in the list. The SinglyLinkedList class has three instance variables, head, tail, and size, that respectively store a reference to the first node in the list, a reference to the last node in the list, and the number of nodes in the list.
The SinglyLinkedList class provides several methods for adding and removing nodes from the list, as well as for getting the size of the list and checking whether the list is empty. The print method is included for printing the contents of the list to the console.
Note that this implementation allows for the creation of a singly linked list of any type by using a generic type parameter T.
The Node class is a private inner class of the SinglyLinkedList class, and it defines a node in the singly linked list. Each Node object has two instance variables: data, which stores the element of data contained in the node, and next, which stores a reference to the next node in the list.
The Node class also has a constructor that takes a data parameter and initializes the data instance variable. The next instance variable is initialized to null by default.
DOUBLY LINKED LISTS
A doubly linked list is a data structure that consists of a sequence of nodes, where each node contains an element of data and references (or pointers) to the previous and next nodes in the sequence. The first node in the sequence is called the head, and the last node is called the tail. In a doubly linked list, traversal is allowed in both directions, from the head to the tail and from the tail to the head.
Here's an example implementation of a doubly linked list in Java:
public class DoublyLinkedList<T> {
private Node<T> head;
private Node<T> tail;
private int size;
private static class Node<T> {
T data;
Node<T> prev;
Node<T> next;
Node(T data) {
this.data = data;
}
}
public DoublyLinkedList() {
head = null;
tail = null;
size = 0;
}
public void addFirst(T data) {
Node<T> node = new Node<>(data);
if (head == null) {
head = node;
tail = node;
} else {
node.next = head;
head.prev = node;
head = node;
}
size++;
}
public void addLast(T data) {
Node<T> node = new Node<>(data);
if (tail == null) {
head = node;
tail = node;
} else {
node.prev = tail;
tail.next = node;
tail = node;
}
size++;
}
public T removeFirst() {
if (head == null) {
return null;
}
T data = head.data;
if (head == tail) {
head = null;
tail = null;
} else {
head = head.next;
head.prev = null;
}
size--;
return data;
}
public T removeLast() {
if (tail == null) {
return null;
}
T data = tail.data;
if (head == tail) {
head = null;
tail = null;
} else {
tail = tail.prev;
tail.next = null;
}
size--;
return data;
}
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
public void clear() {
head = null;
tail = null;
size = 0;
}
public void print() {
Node<T> current = head;
while (current != null) {
System.out.print(current.data + "
");
current = current.next;
}
System.out.println();
}
}
In this implementation, the DoublyLinkedList class has a private inner class Node that defines a node in the list. The DoublyLinkedList class has three instance variables, head, tail, and size, that respectively store references to the first and last nodes in the list, and the number of nodes in the list.
The DoublyLinkedList class provides several methods for adding and removing nodes from the list, as well as for getting the size of the list and checking whether the list is empty. The print method is included for printing the contents of the list to the console.
Note that this implementation allows for the creation of a doubly linked list of any type by using a generic type parameter T.
The Node class is a private inner class of the DoublyLinkedList class, and it defines a node in the doubly linked list. Each Node object has three instance variables: data, which stores the element of data contained in the node, prev, which stores a reference to the previous node in the list, and next, which stores a reference to the next node in the list.
The Node class also has a constructor that takes a data parameter and initializes the data instance variable. The prev and next instance variables are initialized to null by default.
CIRCULAR LINKED LISTS
A circular linked list is a variation of a linked list in which the last node of the list points back to the first node, creating a loop or cycle in the list. This means that there is no end to the list, and traversal can start at any node and continue indefinitely.
Here's an example implementation of a circular linked list in Java:
public class CircularLinkedList<T> {
private Node<T> head;
private int size;
private static class Node<T> {
T data;
Node<T> next;
Node(T data) {
this.data = data;
}
}
public CircularLinkedList() {
head = null;
size = 0;
}
public void addFirst(T data) {
Node<T> node = new Node<>(data);
if (head == null) {
head = node;
head.next = head;
} else {
node.next = head;
Node<T> current = head;
while (current.next != head) {
current =
current.next;
}
current.next = node;
head = node;
}
size++;
}
public void addLast(T data) {
Node<T> node = new Node<>(data);
if (head == null) {
head = node;
head.next = head;
} else {
node.next = head;
Node<T> current = head;
while (current.next != head) {
current =
current.next;
}
current.next = node;
}
size++;
}
public T removeFirst() {
if (head == null) {
return null;
}
T data = head.data;
if (head == head.next) {
head = null;
} else {
Node<T> current = head;
while (current.next != head) {
current =
current.next;
}
current.next = head.next;
head = head.next;
}
size--;
return data;
}
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
public void clear() {
head = null;
size = 0;
}
public void print() {
if (head == null) {
System.out.println("[]");
return;
}
Node<T> current = head;
System.out.print("[");
do {
System.out.print(current.data);
if (current.next != head) {
System.out.print(",
");
}
current = current.next;
} while (current != head);
System.out.println("]");
}
}
In this implementation, the CircularLinkedList class has a private inner class Node that defines a node in the list. The CircularLinkedList class has two instance variables, head and size, that respectively store a reference to the first node in the list and the number of nodes in the list.
The CircularLinkedList class provides several methods for adding and removing nodes from the list, as well as for getting the size of the list and checking whether the list is empty. The print method is included for printing the contents of the list to the console.
Note that in a circular linked list, the next instance variable of the last node in the list points back to the first node. In the implementation, the head instance variable is used to keep track of the first node in the list, and the next instance variable of the last node in the list is set to head.
SKIP LISTS
A skip list is a probabilistic data structure that allows for fast searching of elements in a sorted list. It is similar to a linked list, but with added layers that allow for more efficient traversal of the list.
In a skip list, each node contains a key-value pair (or just a key) and multiple pointers to nodes at lower and higher levels of the list. The lowest level is a regular linked list, with each node having a single next pointer. The higher levels are "skip" levels, with nodes having additional next pointers that "skip" over multiple nodes in the lower level.
Here's an example implementation of a skip list in Java:
public class SkipList<T extends Comparable<T>> {
private final int MAX_LEVEL = 32;
private final double P = 0.5;
private Node<T> head;
private int level;
private static class Node<T> {
T data;
Node<T>[] next;
Node(T data, int level) {
this.data = data;
this.next = new Node[level];
}
}
public SkipList() {
head = new Node<>(null, MAX_LEVEL);
level = 0;
}
public void insert(T data) {
Node<T>[] update = new Node[MAX_LEVEL];
Node<T> current = head;
for (int i = level; i >= 0; i--) {
while (current.next[i] != null &&
current.next[i].data.compareTo(data) < 0) {
current =
current.next[i];
}
update[i] = current;
}
current = current.next[0];
if (current == null || !current.data.equals(data))
{
int newLevel = randomLevel();
if (newLevel > level) {
for (int i = level + 1; i
<= newLevel; i++) {
update[i] =
head;
}
level = newLevel;
}
current = new Node<>(data,
newLevel);
for (int i = 0; i <= newLevel; i++)
{
current.next[i] =
update[i].next[i];
update[i].next[i] =
current;
}
}
}
public void delete(T data) {
Node<T>[] update = new Node[MAX_LEVEL];
Node<T> current = head;
for (int i = level; i >= 0; i--) {
while (current.next[i] != null &&
current.next[i].data.compareTo(data) < 0) {
current =
current.next[i];
}
update[i] = current;
}
current = current.next[0];
if (current != null && current.data.equals(data))
{
for (int i = 0; i <= level; i++)
{
if (update[i].next[i] !=
current) {
break;
}
update[i].next[i] =
current.next[i];
}
while (level > 0 &&
head.next[level] == null) {
level--;
}
}
}
public boolean contains(T data) {
Node<T> current = head;
for (int i = level; i >= 0; i--) {
while (current.next[i] != null &&
current.next[i].data.compareTo(data) < 0) {
current =
current.next[i];
}
}
current = current.next[0];
return current != null &&
current.data.equals(data);
}
private int randomLevel() {
int level = 0;
while (Math.random() < P && level <
MAX_LEVEL - 1) {
level++;
}
return level;
}
}
The SkipList class has a private inner class Node that defines a node in the list. The SkipList class has instance variables for the head node and the current level of the list.
The insert method is used to insert a new node into the list with the given data. The delete method is used to remove a node from the list with the given data. The contains method is used to check if a node with the given data is in the list.
The randomLevel method is used to generate a random level for a new node to be inserted into the list. It does this by repeatedly flipping a biased coin with probability P of landing heads, and incrementing the level until the coin lands tails or the maximum level is reached.
Skip lists are particularly useful for large data sets, as they allow for efficient searching and insertion of data while maintaining a low memory footprint. However, they can be more complex to implement than simple linked lists, and the probabilistic nature of the structure means that the worst-case time complexity is not guaranteed.
PATTERNS
TWO POINTERS/RUNNER TECHNIQUE/FAST & SLOW POINTERS
The Two Pointers/Runner Technique is a common pattern used in problems involving lists. It involves iterating over a list with two pointers, one that moves at a faster pace than the other. This technique is often used to find the midpoint of a list, or to detect cycles in a linked list.
To find the midpoint of a list, we can use the two pointers to traverse the list. One pointer starts at the head of the list and moves one node at a time, while the other pointer starts at the head and moves two nodes at a time. When the faster pointer reaches the end of the list, the slower pointer will be pointing to the middle node of the list.
To detect cycles in a linked list, we can use the two pointers to traverse the list as well. One pointer starts at the head of the list and moves one node at a time, while the other pointer starts at the head and moves two nodes at a time. If there is a cycle in the list, the faster pointer will eventually catch up to the slower pointer, and we can detect the cycle by checking if the two pointers meet.
The Two Pointers/Runner Technique can be an efficient way to solve problems involving lists, as it only requires one pass over the list and doesn't require extra space.
CYCLE IN LINKED LIST
Finding the Cycle in a Linked List is a common pattern used in problems involving lists. It involves detecting if a linked list has a cycle, and if so, determining the starting node of the cycle. This can be useful in solving problems that require detecting cycles in data structures or finding the starting point of a circular structure.
To detect if a linked list has a cycle, we can use the Floyd's Cycle Detection Algorithm, also known as the "tortoise and hare" algorithm. It involves using two pointers, a slow pointer and a fast pointer, to traverse the list. The slow pointer moves one node at a time, while the fast pointer moves two nodes at a time. If there is a cycle in the list, the fast pointer will eventually catch up to the slow pointer, indicating the presence of a cycle.
Once we detect a cycle, we can determine the starting node of the cycle by resetting one of the pointers to the head of the list, and then moving both pointers at the same pace until they meet at the starting node of the cycle.
For example, let's say we have the following linked list with a cycle:
1 -> 2 -> 3 -> 4 -> 5 -> 3
To detect the cycle, we can initialize a slow pointer and a fast pointer to the head of the list. We move the slow pointer one node at a time, and the fast pointer two nodes at a time. If there is a cycle in the list, the fast pointer will eventually catch up to the slow pointer.
Here's an example implementation in Java:
public ListNode detectCycle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
break;
}
}
if (fast == null || fast.next == null) {
return null; // no cycle
}
slow = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
After detecting the cycle, the starting node of the cycle will be 3.
By finding the cycle in a linked list, we can efficiently solve problems that require detecting cycles in data structures or finding the starting point of a circular structure.
REVERSE A LINKED LIST
Reversing a List is a common pattern used in problems involving lists. It involves reversing the order of elements in a list. This can be useful in solving problems that require iterating over a list backwards or finding the nth-to-last element of a list.
To reverse a list, we can use a two-pointer technique to traverse the list. One pointer starts at the head of the list, and the other pointer starts at the end of the list. We swap the data of the two pointers and move them towards each other until they meet in the middle. After we finish the traversal, the list will be reversed.
For example, let's say we have the following linked list:
1 -> 2 -> 3 -> 4 -> 5 -> null
To reverse the list, we can initialize two pointers prev and current, where prev starts as null and current starts as the head of the list. We iterate through the list, swapping the current node's next pointer to point to the prev node, then updating prev to be the current node, and current to be the next node. We continue this process until we reach the end of the list.
Here's an example implementation in Java:
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode current = head;
while (current != null) {
ListNode next = current.next;
current.next = prev;
prev = current;
current = next;
}
return prev;
}
After reversing the list, the new list will be:
5 -> 4 -> 3 -> 2 -> 1 -> null
By reversing the list, we can efficiently solve problems that require iterating over a list backwards, or finding the nth-to-last element of a list.
MERGE TWO LISTS
Merging Two Lists is a common pattern used in problems involving lists. It involves combining two sorted lists into a single sorted list. This can be useful in solving problems that require sorting or merging multiple lists.
To merge two sorted lists, we can use a two-pointer technique to traverse both lists simultaneously. We compare the current nodes in both lists, and add the smaller node to the result list. We then move the pointer of the smaller node to the next node in its list, and repeat the process until we reach the end of one of the lists. We then append the remaining nodes in the other list to the result list.
For example, let's say we have two sorted linked lists:
list1: 1 -> 3 -> 5 -> 7 -> null
list2: 2 -> 4 -> 6 -> null
To merge the two lists, we can initialize a dummy node and two pointers p1 and p2, where p1 and p2 start as the heads of list1 and list2, respectively. We iterate through both lists, adding the smaller node to the result list and moving the pointer of the smaller node to the next node in its list. We continue this process until we reach the end of one of the lists.
Here's an example implementation in Java:
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
ListNode p1 = l1, p2 = l2;
while (p1 != null && p2 != null) {
if (p1.val < p2.val) {
tail.next = p1;
p1 = p1.next;
} else {
tail.next = p2;
p2 = p2.next;
}
tail = tail.next;
}
if (p1 != null) {
tail.next = p1;
} else {
tail.next = p2;
}
return dummy.next;
}
After merging the two lists, the new list will be:
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> null
By merging two sorted lists, we can efficiently solve problems that require sorting or merging multiple lists.
INTERSECTION OF TWO LISTS
Finding the Intersection of Two Lists is a common pattern used in problems involving lists. It involves finding the common elements between two lists. This can be useful in solving problems that require finding common elements or comparing two sets of data.
To find the intersection of two lists, we can use a hash table or a two-pointer technique to traverse both lists. If one of the lists is significantly smaller than the other, we can create a hash table with the elements in the smaller list, and then iterate over the larger list and check if each element is in the hash table. If both lists are of similar size, we can use a two-pointer technique to traverse both lists simultaneously, comparing the current nodes in both lists and adding the common nodes to the result list.
For example, let's say we have the following two linked lists:
list1: 1 -> 2 -> 3 -> 4 -> 5 -> null
list2: 4 -> 5 -> 6 -> 7 -> 8 -> null
To find the intersection of the two lists, we can use a hash table to store the elements in list1, and then iterate over list2 and check if each element is in the hash table. If an element is in the hash table, we add it to the result list.
Here's an example implementation in Java:
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
Set<ListNode> set = new HashSet<>();
ListNode currA = headA;
while (currA != null) {
set.add(currA);
currA = currA.next;
}
ListNode currB = headB;
while (currB != null) {
if (set.contains(currB)) {
return currB;
}
currB = currB.next;
}
return null;
}
After finding the intersection of the two lists, the result will be:
4 -> 5 -> null
By finding the intersection of two lists, we can efficiently solve problems that require finding common elements or comparing two sets of data.
PARTITION LISTS
Partition List is a common pattern used in problems involving linked lists. It involves partitioning a linked list around a specific value. This can be useful in solving problems that require separating a list into two parts based on a specific value or condition.
To partition a linked list, we can use a two-pointer technique to traverse the list. We maintain two pointers, a before pointer and an after pointer, which point to the heads of two separate lists. We then iterate through the original list, adding nodes to either the before list or the after list depending on whether their values are less than or greater than the partition value. Finally, we combine the two lists by pointing the last node in the before list to the head of the after list.
For example, let's say we have the following linked list:
1 -> 4 -> 3 -> 2 -> 5 -> 2
We want to partition the list around the value 3, so that all nodes with values less than 3 come before all nodes with values greater than or equal to 3. The resulting list should look like this:
1 -> 2 -> 2 -> 4 -> 3 -> 5
To partition the list, we can initialize a before pointer and an after pointer to the heads of two separate lists. We iterate through the original list, adding nodes to either the before list or the after list depending on whether their values are less than or greater than the partition value. Finally, we combine the two lists by pointing the last node in the before list to the head of the after list.
Here's an example implementation in Java:
public ListNode partition(ListNode head, int x) {
ListNode before = new ListNode(0);
ListNode after = new ListNode(0);
ListNode p1 = before, p2 = after;
while (head != null) {
if (head.val < x) {
p1.next = head;
p1 = p1.next;
} else {
p2.next = head;
p2 = p2.next;
}
head = head.next;
}
p2.next = null;
p1.next = after.next;
return before.next;
}
After partitioning the list, the resulting list will be:
1 -> 2 -> 2 -> 4 -> 3 -> 5
By partitioning a linked list, we can efficiently solve problems that require separating a list into two parts based on a specific value or condition.
PROBLEMS
Easy
Medium
- Add Two Numbers
- Partition List
- Swap Nodes in Pairs
- Intersection of Two Linked Lists
- Palindrome Linked List
- Odd Even Linked List
Hard