LinkedList Flashcards
How to import and initialize a Linked List
import java.util.LinkedList;
LinkedList<DataType> Name = new LinkedList<>();</DataType>
O(n)
Access, Search, delete value
O(1)
Insert at head and tail
How to add to head/tail and remove from head/tail
addFirst(E e)
addLast(E e)
removeFirst()
removeLast()
How to get an element at linked list index
linkedList.get(i);
What benefits are in a linked list as opposed to an array?
A linked list
Show me how to create the node class
You need the constructor
private static class Node(){
int data;
Node next;
Node(int data){
this.data = data;
this.next = null;
}
}
What must you always include so that all other methods can access in a linked list?
The head node
Why is the node class private and static?
Private so nothing else can mess with our constructor
Static so that it is independent of the linked list’s object
Show me code to insert a node at the end
public void insert(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
return;
}
Node current = head;
while (current.next != null) {
current = current.next;
}
current.next = newNode;
}
Show me how to insert a node at the beginning
public void insertAtBeginning(int data) {
Node newNode = new Node(data);
newNode.next = head;
head = newNode;
}
Show me how to insert at a index
// Insert at a specific position
public void insertAt(int index, int data) {
if (index < 0) return;
Node newNode = new Node(data);
if (index == 0) {
newNode.next = head;
head = newNode;
return;
}
Node current = head;
for (int i = 0; current != null && i < index - 1; i++) {
current = current.next;
}
if (current == null) return;
newNode.next = current.next;
current.next = newNode;
}
Show me how to delete at an index
// Delete at a specific position
public void deleteAt(int index) {
if (head == null || index < 0) return;
if (index == 0) {
head = head.next;
return;
}
Node current = head;
for (int i = 0; current.next != null && i < index - 1; i++) {
current = current.next;
}
if (current.next == null) return;
current.next = current.next.next;
}
Show me how to delete a node by data
// Delete a node by value
public void delete(int data) {
if (head == null) return;
if (head.data == data) {
head = head.next;
return;
}
Node current = head;
while (current.next != null && current.next.data != data) {
current = current.next;
}
if (current.next != null) {
current.next = current.next.next;
}
}
Show me how to search for a data
// Search for an element
public boolean search(int data) {
Node current = head;
while (current != null) {
if (current.data == data) return true;
current = current.next;
}
return false;
}
Show me how to find length of a list
// Find the length of the list
public int size() {
int count = 0;
Node current = head;
while (current != null) {
count++;
current = current.next;
}
return count;
}
Show me how to reverse a list
// Reverse the linked list
public void reverse() {
Node prev = null, current = head, next;
while (current != null) {
next = current.next;
current.next = prev;
prev = current;
current = next;
}
head = prev;
}
Show me how to display an entire node
// Display the linked list
public void display() {
Node current = head;
while (current != null) {
System.out.print(current.data + “ -> “);
current = current.next;
}
System.out.println(“null”);
}
What is the pattern to iterate through a linked list?
- Create a new node and set it to head
- A while loop that while newNode.next != null
- newNode = newNode.next
- Decide if you want to delete or add it
What is the pattern to add a node
currentNode.next = currentNode
What is the pattern to delete a node
currentNode.next = currentNode.next.next
