The LinkedList class in Java is a built-in data structure that implements the List interface. It represents a linked list, which is a data structure that consists of a sequence of nodes, each containing a reference to the next node in the list.
Here is an example of how to create a LinkedList in Java:
import java.util.LinkedList;
public class Main {
public static void main(String[] args) {
LinkedList<String> list = new LinkedList<String>();
list.add("Apple");
list.add("Banana");
list.add("Cherry");
System.out.println(list);
}
}
In this example, we first import the LinkedList class from the java.util package. Then, we create a new LinkedList object and add three elements to it using the add() method. Finally, we print the contents of the list using the println() method.
Some of the methods available in the LinkedList class include:
- add(element): adds an element to the end of the list.
- add(index, element): adds an element at the specified index.
- get(index): returns the element at the specified index.
- remove(index): removes the element at the specified index.
- size(): returns the number of elements in the list.
LinkedLists have some advantages over arrays in terms of adding and removing elements from the beginning or end of the list, but they can be slower when accessing elements in the middle of the list.
Hierarchy of LinkedList class:
The LinkedList class in Java extends the AbstractSequentialList class and implements the List and Deque interfaces. This creates a hierarchy of class relationships as follows:
java.lang.Object
|
+--java.util.AbstractCollection<E>
|
+--java.util.AbstractList<E>
|
+--java.util.AbstractSequentialList<E>
|
+--java.util.LinkedList<E>
- The Object class is the root of the class hierarchy in Java.
- The AbstractCollection class provides a skeletal implementation of the Collection interface.
- The AbstractList class provides a skeletal implementation of the List interface, including methods for accessing and modifying elements.
- The AbstractSequentialList class provides a skeletal implementation of the List interface for sequential access data structures.
- The LinkedList class is a concrete implementation of the List and Deque interfaces using a doubly-linked list.
The LinkedList class inherits methods from each of its superclasses, allowing it to provide a wide range of functionality for working with linked lists.
Doubly Linked List:
A doubly linked list is a type of linked list where each node in the list contains not only a reference to the next node in the list, but also a reference to the previous node. This allows for bidirectional traversal of the list, meaning that it can be iterated over in both forward and backward directions.
In a doubly linked list, each node has the following structure:
class Node {
Object data;
Node next;
Node prev;
}
The data field contains the value stored in the node, while the next and prev fields contain references to the next and previous nodes in the list, respectively.
Here is an example implementation of a doubly linked list in Java:
class DoublyLinkedList {
private Node head;
private Node tail;
private class Node {
Object data;
Node next;
Node prev;
}
public void add(Object item) {
Node newNode = new Node();
newNode.data = item;
newNode.prev = tail;
if (tail != null) {
tail.next = newNode;
} else {
head = newNode;
}
tail = newNode;
}
public void remove(Object item) {
Node current = head;
while (current != null) {
if (current.data.equals(item)) {
if (current.prev != null) {
current.prev.next = current.next;
} else {
head = current.next;
}
if (current.next != null) {
current.next.prev = current.prev;
} else {
tail = current.prev;
}
break;
}
current = current.next;
}
}
}
In this implementation, the DoublyLinkedList class has a private nested Node class for representing nodes in the list. The add method adds a new node to the end of the list, while the remove method removes the first node in the list that contains the specified item.
Doubly linked lists have advantages over singly linked lists in terms of bidirectional traversal and efficient removal of nodes. However, they require more memory due to the extra reference field in each node, and can be slightly slower in some operations due to the extra pointer manipulation required.
LinkedList class declaration:
The LinkedList class in Java is declared in the java.util package. Here is its declaration:
public class LinkedList<E> extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable {
// class implementation
}
The LinkedList class is a generic class, as indicated by the <E> in the class declaration. This means that you can create a LinkedList of any type of object, as long as the type is specified when the list is created. For example, you can create a LinkedList of integers like this:
LinkedList<Integer> list = new LinkedList<Integer>();
The LinkedList class extends the AbstractSequentialList class, which provides a skeletal implementation of the List interface for sequential access data structures. It also implements the List, Deque, Cloneable, and Serializable interfaces, which provide various additional functionality.
Some of the important methods available in the LinkedList class include:
add(E element): adds an element to the end of the list.add(int index, E element): adds an element at the specified index.get(int index): returns the element at the specified index.remove(int index): removes the element at the specified index.size(): returns the number of elements in the list.iterator(): returns an iterator over the elements in the list.descendingIterator(): returns an iterator over the elements in the list in reverse order.
The LinkedList class also provides several methods for manipulating the first and last elements in the list, such as addFirst, addLast, getFirst, getLast, removeFirst, and removeLast. These methods are provided to support the Deque interface, which extends the Queue interface and provides additional methods for manipulating the elements at the beginning and end of a queue.
Constructors of Java LinkedList:
The LinkedList class in Java provides several constructors that allow you to create a new linked list object. Here are the constructors provided by the LinkedList class:
LinkedList(): Creates an empty linked list.LinkedList(Collection<? extends E> c): Creates a linked list containing the elements of the specified collection, in the order they are returned by the collection’s iterator.LinkedList(E[] array): Creates a linked list containing the elements of the specified array, in the order they appear in the array.
Example usage of the constructors:
// create an empty linked list
LinkedList<Integer> list1 = new LinkedList<Integer>();
// create a linked list from an array
Integer[] array = {1, 2, 3};
LinkedList<Integer> list2 = new LinkedList<Integer>(array);
// create a linked list from a collection
List<Integer> collection = Arrays.asList(4, 5, 6);
LinkedList<Integer> list3 = new LinkedList<Integer>(collection);
In the first example, an empty LinkedList object is created using the default constructor. In the second example, a LinkedList object is created from an array of integers, with the elements added to the list in the order they appear in the array. In the third example, a LinkedList object is created from a List collection of integers, with the elements added to the list in the order they are returned by the collection’s iterator.
Note that since the LinkedList class is a generic class, the type parameter is specified when creating a new instance of the class, as shown in the examples above. In this way, you can create linked lists of any type of object.
Methods of Java LinkedList:
The LinkedList class in Java provides a wide range of methods for manipulating the linked list. Here are some of the most commonly used methods:
add(E element): Adds the specified element to the end of the list.add(int index, E element): Inserts the specified element at the specified position in the list.addAll(Collection<? extends E> c): Adds all of the elements in the specified collection to the end of the list.addAll(int index, Collection<? extends E> c): Inserts all of the elements in the specified collection into the list at the specified position.clear(): Removes all of the elements from the list.contains(Object o): Returns true if the list contains the specified element.get(int index): Returns the element at the specified position in the list.indexOf(Object o): Returns the index of the first occurrence of the specified element in the list, or -1 if the list does not contain the element.isEmpty(): Returns true if the list contains no elements.iterator(): Returns an iterator over the elements in the list.remove(Object o): Removes the first occurrence of the specified element from the list, if it is present.remove(int index): Removes the element at the specified position in the list.removeFirst(): Removes and returns the first element from the list.removeLast(): Removes and returns the last element from the list.size(): Returns the number of elements in the list.toArray(): Returns an array containing all of the elements in the list.
In addition to these methods, the LinkedList class also provides several methods for manipulating the first and last elements of the list, such as getFirst(), getLast(), addFirst(E element), and addLast(E element). The LinkedList class also implements the Deque interface, which provides additional methods for manipulating the elements at the beginning and end of the list.
Overall, the LinkedList class provides a wide range of methods for manipulating linked lists, making it a versatile and powerful tool for working with linked data structures in Java.
Java LinkedList Example:
Sure, here’s an example of how to use the Java LinkedList class:
import java.util.LinkedList;
public class LinkedListExample {
public static void main(String[] args) {
// create a new linked list
LinkedList<String> list = new LinkedList<String>();
// add elements to the list
list.add("Alice");
list.add("Bob");
list.add("Charlie");
// print the size of the list
System.out.println("Size of the list: " + list.size());
// print the contents of the list
System.out.println("Contents of the list: " + list);
// insert an element at a specific position
list.add(1, "David");
// print the contents of the list after inserting an element
System.out.println("Contents of the list after inserting an element: " + list);
// remove an element from the list
list.remove("Charlie");
// print the contents of the list after removing an element
System.out.println("Contents of the list after removing an element: " + list);
// get an element from the list
String element = list.get(2);
System.out.println("Element at position 2: " + element);
// clear the list
list.clear();
// check if the list is empty
System.out.println("Is the list empty? " + list.isEmpty());
}
}
This code creates a new LinkedList object, adds three elements to it, prints the size and contents of the list, inserts an element at a specific position, removes an element from the list, gets an element from the list, clears the list, and checks if the list is empty.
When you run this code, you should see the following output:
Size of the list: 3 Contents of the list: [Alice, Bob, Charlie] Contents of the list after inserting an element: [Alice, David, Bob, Charlie] Contents of the list after removing an element: [Alice, David, Bob] Element at position 2: Bob Is the list empty? true
This example demonstrates some of the basic operations you can perform on a linked list using the LinkedList class in Java.
Java LinkedList example to add elements:
Sure, here’s an example of how to add elements to a Java LinkedList:
import java.util.LinkedList;
public class AddElementsToLinkedListExample {
public static void main(String[] args) {
// create a new linked list
LinkedList<String> list = new LinkedList<String>();
// add elements to the list
list.add("Alice");
list.add("Bob");
list.add("Charlie");
// print the contents of the list
System.out.println("Contents of the list: " + list);
// add an element to the beginning of the list
list.addFirst("David");
// print the contents of the list after adding an element to the beginning
System.out.println("Contents of the list after adding an element to the beginning: " + list);
// add an element to the end of the list
list.addLast("Emily");
// print the contents of the list after adding an element to the end
System.out.println("Contents of the list after adding an element to the end: " + list);
// add an element at a specific position
list.add(2, "Frank");
// print the contents of the list after adding an element at a specific position
System.out.println("Contents of the list after adding an element at a specific position: " + list);
}
}
This code creates a new LinkedList object, adds three elements to it, prints the contents of the list, adds an element to the beginning of the list, adds an element to the end of the list, adds an element at a specific position, and prints the contents of the list after each operation.
When you run this code, you should see the following output:
Contents of the list: [Alice, Bob, Charlie] Contents of the list after adding an element to the beginning: [David, Alice, Bob, Charlie] Contents of the list after adding an element to the end: [David, Alice, Bob, Charlie, Emily] Contents of the list after adding an element at a specific position: [David, Alice, Frank, Bob, Charlie, Emily]
This example demonstrates how to use the add(), addFirst(), addLast(), and add(int index, E element) methods to add elements to a Java LinkedList.
Java LinkedList example to remove elements:
Sure, here’s an example of how to remove elements from a Java LinkedList:
import java.util.LinkedList;
public class RemoveElementsFromLinkedListExample {
public static void main(String[] args) {
// create a new linked list
LinkedList<String> list = new LinkedList<String>();
// add elements to the list
list.add("Alice");
list.add("Bob");
list.add("Charlie");
list.add("David");
list.add("Emily");
// print the contents of the list
System.out.println("Contents of the list: " + list);
// remove the first element from the list
String first = list.removeFirst();
// print the contents of the list after removing the first element
System.out.println("Contents of the list after removing the first element (" + first + "): " + list);
// remove the last element from the list
String last = list.removeLast();
// print the contents of the list after removing the last element
System.out.println("Contents of the list after removing the last element (" + last + "): " + list);
// remove an element at a specific position
String removed = list.remove(2);
// print the contents of the list after removing an element at a specific position
System.out.println("Contents of the list after removing an element at a specific position (" + removed + "): " + list);
// remove a specific element from the list
boolean removedElement = list.remove("Bob");
// print the contents of the list after removing a specific element
System.out.println("Contents of the list after removing a specific element (Bob): " + list);
}
}
This code creates a new LinkedList object, adds five elements to it, prints the contents of the list, removes the first element from the list, removes the last element from the list, removes an element at a specific position, removes a specific element from the list, and prints the contents of the list after each operation.
When you run this code, you should see the following output:
Contents of the list: [Alice, Bob, Charlie, David, Emily] Contents of the list after removing the first element (Alice): [Bob, Charlie, David, Emily] Contents of the list after removing the last element (Emily): [Bob, Charlie, David] Contents of the list after removing an element at a specific position (Charlie): [Bob, David] Contents of the list after removing a specific element (Bob): [David]
This example demonstrates how to use the remove(), removeFirst(), removeLast(), and remove(int index) methods to remove elements from a Java LinkedList.
Java LinkedList Example to reverse a list of elements:
Sure, here’s an example of how to reverse a Java LinkedList:
import java.util.LinkedList;
import java.util.Collections;
public class ReverseLinkedListExample {
public static void main(String[] args) {
// create a new linked list
LinkedList<String> list = new LinkedList<String>();
// add elements to the list
list.add("Alice");
list.add("Bob");
list.add("Charlie");
list.add("David");
list.add("Emily");
// print the contents of the list
System.out.println("Contents of the list: " + list);
// reverse the order of the elements in the list
Collections.reverse(list);
// print the contents of the list after reversing the order of the elements
System.out.println("Contents of the list after reversing the order of the elements: " + list);
}
}
This code creates a new LinkedList object, adds five elements to it, prints the contents of the list, reverses the order of the elements in the list using the Collections.reverse() method, and prints the contents of the list after reversing the order of the elements.
When you run this code, you should see the following output:
Contents of the list: [Alice, Bob, Charlie, David, Emily] Contents of the list after reversing the order of the elements: [Emily, David, Charlie, Bob, Alice]
This example demonstrates how to use the Collections.reverse() method to reverse the order of the elements in a Java LinkedList.
Java LinkedList Example: Book
Sure, here’s an example of how to use a Java LinkedList to store and manipulate a collection of Book objects:
import java.util.LinkedList;
public class Book {
private String title;
private String author;
private int year;
public Book(String title, String author, int year) {
this.title = title;
this.author = author;
this.year = year;
}
public String getTitle() {
return title;
}
public String getAuthor() {
return author;
}
public int getYear() {
return year;
}
public String toString() {
return "Book [title=" + title + ", author=" + author + ", year=" + year + "]";
}
public static void main(String[] args) {
// create a new linked list to store books
LinkedList<Book> books = new LinkedList<Book>();
// create some book objects and add them to the list
Book book1 = new Book("The Great Gatsby", "F. Scott Fitzgerald", 1925);
Book book2 = new Book("To Kill a Mockingbird", "Harper Lee", 1960);
Book book3 = new Book("1984", "George Orwell", 1949);
Book book4 = new Book("Pride and Prejudice", "Jane Austen", 1813);
Book book5 = new Book("The Catcher in the Rye", "J.D. Salinger", 1951);
books.add(book1);
books.add(book2);
books.add(book3);
books.add(book4);
books.add(book5);
// print the contents of the list
System.out.println("Contents of the list: " + books);
// remove a book from the list
books.remove(book3);
// print the contents of the list after removing a book
System.out.println("Contents of the list after removing a book: " + books);
// add a new book to the beginning of the list
Book book6 = new Book("The Hobbit", "J.R.R. Tolkien", 1937);
books.addFirst(book6);
// print the contents of the list after adding a new book to the beginning
System.out.println("Contents of the list after adding a new book to the beginning: " + books);
}
}
This code defines a Book class with fields for the title, author, and year, as well as a toString() method for printing book objects in a readable format. It then creates a new LinkedList object to store Book objects, creates some Book objects, adds them to the list, and prints the contents of the list.
The code then removes a book from the list, prints the contents of the list again, adds a new book to the beginning of the list, and prints the contents of the list one final time.
When you run this code, you should see the following output:
Contents of the list: [Book [title=The Great Gatsby, author=F. Scott Fitzgerald, year=1925], Book [title=To Kill a Mockingbird, author=Harper Lee, year=1960], Book [title=1984, author=George Orwell, year=1949], Book [title=Pride and Prejudice, author=Jane Austen, year=1813], Book [title=The Catcher in the Rye, author=J.D. Salinger, year=1951]] Contents of the list after removing a book: [Book [title=The Great Gatsby, author=F. Scott Fitzgerald, year=192