Java LinkedList类 _Java数据结构

文章图片
Java LinkedList类使用双链表来存储元素。它提供了一个链表数据结构。它继承了AbstractList类并实现List和Deque接口。
关于Java LinkedList的要点是：

Java LinkedList类可以包含重复的元素。
Java LinkedList类维护插入顺序。
Java LinkedList类不同步。
在Java LinkedList类中, 操作是快速的, 因为不需要进行任何移位。
Java LinkedList类可以用作列表, 堆栈或队列。

LinkedList类的层次结构
如上图所示, Java LinkedList类扩展了AbstractSequentialList类并实现了List和Deque接口。
双链表
在双向链表的情况下, 我们可以从两侧添加或删除元素。

文章图片
LinkedList类声明
我们来看一下java.util.LinkedList类的声明。

public class LinkedList< E> extends AbstractSequentialList< E> implements List< E> , Deque< E> , Cloneable, Serializable

Java LinkedList的构造方法

建设者	描述
LinkedList()	它用于构造一个空列表。
LinkedList（Collection < ？扩展E> c）	它用于构造一个包含指定集合元素的列表, 这些元素按顺序由集合的迭代器返回。

Java LinkedList的方法

方法	描述
boolean add(E e)	它用于将指定的元素附加到列表的末尾。
void add(int index, E element)	用于将指定的元素插入列表中指定位置的索引处。
布尔addAll（Collection < ？扩展E> c）	它用于将指定集合中的所有元素附加到此列表的末尾, 以指定集合的??迭代器返回它们的顺序。
布尔addAll（Collection < ？扩展E> c）	它用于将指定集合中的所有元素附加到此列表的末尾, 以指定集合的??迭代器返回它们的顺序。
布尔addAll（int索引, Collection < ？扩展E> c）	从列表的指定位置开始, 它用于附加指定集合中的所有元素。
void addFirst(E e)	它用于将给定元素插入列表的开头。
void addLast(E e)	它用于将给定元素附加到列表的末尾。
void clear()	它用于从列表中删除所有元素。
Object clone()	它用于返回ArrayList的浅表副本。
boolean contains(Object o)	如果列表包含指定的元素, 则用于返回true。
Iterator< E> descendingIterator()	它用于以相反的顺序在双端队列中返回元素上的迭代器。
E element()	它用于检索列表的第一个元素。
E get(int index)	它用于返回列表中指定位置的元素。
E getFirst()	它用于返回列表中的第一个元素。
E getLast()	它用于返回列表中的最后一个元素。
int indexOf(Object o)	它用于返回指定元素首次出现的列表中的索引；如果列表不包含任何元素, 则返回-1。
int lastIndexOf(Object o)	它用于返回指定元素最后一次出现的列表中的索引；如果列表不包含任何元素, 则返回-1。
ListIterator < E> listIterator（int索引）	从列表中的指定位置开始, 它用于按正确顺序返回元素的列表迭代器。
boolean offer(E e)	它将指定的元素添加为列表的最后一个元素。
boolean offerFirst(E e)	它将指定的元素插入列表的开头。
boolean offerLast(E e)	它将指定的元素插入列表的末尾。
E peek()	它检索列表的第一个元素
E peekFirst()	它检索列表的第一个元素；如果列表为空, 则返回null。
E peekLast()	它检索列表的最后一个元素；如果列表为空, 则返回null。
E poll()	它检索并删除列表的第一个元素。
E pollFirst()	它检索并删除列表的第一个元素, 如果列表为空, 则返回null。
E pollLast()	它检索并删除列表的最后一个元素, 如果列表为空, 则返回null。
E pop()	它从列表表示的堆栈中弹出一个元素。
void push(E e)	它将元素压入列表表示的堆栈。
E remove()	它用于检索和删除列表的第一个元素。
E remove(int index)	用于删除列表中指定位置的元素。
boolean remove(Object o)	它用于删除列表中指定元素的首次出现。
E removeFirst()	它从列表中删除并返回第一个元素。
boolean removeFirstOccurrence(Object o)	它用于删除列表中指定元素的首次出现（当从头到尾遍历列表时）。
E removeLast()	它从列表中删除并返回最后一个元素。
boolean removeLastOccurrence(Object o)	它删除列表中最后一次出现的指定元素（从头到尾遍历列表时）。
E set(int index, E element)	它将列表中指定位置的元素替换为指定元素。
Object[] toArray()	它用于返回一个包含列表中所有元素的数组, 并按适当的顺序排列（从第一个元素到最后一个元素）。
< T> T [] toArray（T [] a）	它返回一个数组, 该数组包含按正确顺序排列的所有元素（从第一个元素到最后一个元素）；返回数组的运行时类型是指定数组的运行时类型。
int size()	它用于返回列表中元素的数量。

Java LinkedList示例

import java.util.*; public class LinkedList1{ public static void main(String args[]){LinkedList< String> al=new LinkedList< String> (); al.add("Ravi"); al.add("Vijay"); al.add("Ravi"); al.add("Ajay"); Iterator< String> itr=al.iterator(); while(itr.hasNext()){ System.out.println(itr.next()); } } }

Output: Ravi Vijay Ravi Ajay

Java LinkedList示例添加元素
在这里, 我们看到了添加元素的不同方法。

import java.util.*; public class LinkedList2{ public static void main(String args[]){ LinkedList< String> ll=new LinkedList< String> (); System.out.println("Initial list of elements: "+ll); ll.add("Ravi"); ll.add("Vijay"); ll.add("Ajay"); System.out.println("After invoking add(E e) method: "+ll); //Adding an element at the specific position ll.add(1, "Gaurav"); System.out.println("After invoking add(int index, E element) method: "+ll); LinkedList< String> ll2=new LinkedList< String> (); ll2.add("Sonoo"); ll2.add("Hanumat"); //Adding second list elements to the first list ll.addAll(ll2); System.out.println("After invoking addAll(Collection< ? extends E> c) method: "+ll); LinkedList< String> ll3=new LinkedList< String> (); ll3.add("John"); ll3.add("Rahul"); //Adding second list elements to the first list at specific position ll.addAll(1, ll3); System.out.println("After invoking addAll(int index, Collection< ? extends E> c) method: "+ll); //Adding an element at the first position ll.addFirst("Lokesh"); System.out.println("After invoking addFirst(E e) method: "+ll); //Adding an element at the last position ll.addLast("Harsh"); System.out.println("After invoking addLast(E e) method: "+ll); } }

Initial list of elements: [] After invoking add(E e) method: [Ravi, Vijay, Ajay] After invoking add(int index, E element) method: [Ravi, Gaurav, Vijay, Ajay] After invoking addAll(Collection< ? extends E> c) method: [Ravi, Gaurav, Vijay, Ajay, Sonoo, Hanumat] After invoking addAll(int index, Collection< ? extends E> c) method: [Ravi, John, Rahul, Gaurav, Vijay, Ajay, Sonoo, Hanumat] After invoking addFirst(E e) method: [Lokesh, Ravi, John, Rahul, Gaurav, Vijay, Ajay, Sonoo, Hanumat] After invoking addLast(E e) method: [Lokesh, Ravi, John, Rahul, Gaurav, Vijay, Ajay, Sonoo, Hanumat, Harsh]

Java LinkedList示例删除元素
【Java LinkedList类】在这里, 我们看到了删除元素的不同方法。

import java.util.*; public class LinkedList3 {public static void main(String [] args) { LinkedList< String> ll=new LinkedList< String> (); ll.add("Ravi"); ll.add("Vijay"); ll.add("Ajay"); ll.add("Anuj"); ll.add("Gaurav"); ll.add("Harsh"); ll.add("Virat"); ll.add("Gaurav"); ll.add("Harsh"); ll.add("Amit"); System.out.println("Initial list of elements: "+ll); //Removing specific element from arraylist ll.remove("Vijay"); System.out.println("After invoking remove(object) method: "+ll); //Removing element on the basis of specific position ll.remove(0); System.out.println("After invoking remove(index) method: "+ll); LinkedList< String> ll2=new LinkedList< String> (); ll2.add("Ravi"); ll2.add("Hanumat"); // Adding new elements to arraylist ll.addAll(ll2); System.out.println("Updated list : "+ll); //Removing all the new elements from arraylist ll.removeAll(ll2); System.out.println("After invoking removeAll() method: "+ll); //Removing first element from the list ll.removeFirst(); System.out.println("After invoking removeFirst() method: "+ll); //Removing first element from the list ll.removeLast(); System.out.println("After invoking removeLast() method: "+ll); //Removing first occurrence of element from the list ll.removeFirstOccurrence("Gaurav"); System.out.println("After invoking removeFirstOccurrence() method: "+ll); //Removing last occurrence of element from the list ll.removeLastOccurrence("Harsh"); System.out.println("After invoking removeLastOccurrence() method: "+ll); //Removing all the elements available in the list ll.clear(); System.out.println("After invoking clear() method: "+ll); } }

Initial list of elements: [Ravi, Vijay, Ajay, Anuj, Gaurav, Harsh, Virat, Gaurav, Harsh, Amit] After invoking remove(object) method: [Ravi, Ajay, Anuj, Gaurav, Harsh, Virat, Gaurav, Harsh, Amit] After invoking remove(index) method: [Ajay, Anuj, Gaurav, Harsh, Virat, Gaurav, Harsh, Amit] Updated list : [Ajay, Anuj, Gaurav, Harsh, Virat, Gaurav, Harsh, Amit, Ravi, Hanumat] After invoking removeAll() method: [Ajay, Anuj, Gaurav, Harsh, Virat, Gaurav, Harsh, Amit] After invoking removeFirst() method: [Gaurav, Harsh, Virat, Gaurav, Harsh, Amit] After invoking removeLast() method: [Gaurav, Harsh, Virat, Gaurav, Harsh] After invoking removeFirstOccurrence() method: [Harsh, Virat, Gaurav, Harsh] After invoking removeLastOccurrence() method: [Harsh, Virat, Gaurav] After invoking clear() method: []

Java LinkedList示例, 以反转元素列表

import java.util.*; public class LinkedList4{ public static void main(String args[]){LinkedList< String> ll=new LinkedList< String> (); ll.add("Ravi"); ll.add("Vijay"); ll.add("Ajay"); //Traversing the list of elements in reverse order Iterator i=ll.descendingIterator(); while(i.hasNext()) { System.out.println(i.next()); } } }

Output: Ajay Vijay Ravi

Java LinkedList示例：书籍

import java.util.*; class Book { int id; String name, author, publisher; int quantity; public Book(int id, String name, String author, String publisher, int quantity) { this.id = id; this.name = name; this.author = author; this.publisher = publisher; this.quantity = quantity; } } public class LinkedListExample { public static void main(String[] args) { //Creating list of Books List< Book> list=new LinkedList< Book> (); //Creating Books Book b1=new Book(101, "Let us C", "Yashwant Kanetkar", "BPB", 8); Book b2=new Book(102, "Data Communications & Networking", "Forouzan", "Mc Graw Hill", 4); Book b3=new Book(103, "Operating System", "Galvin", "Wiley", 6); //Adding Books to list list.add(b1); list.add(b2); list.add(b3); //Traversing list for(Book b:list){ System.out.println(b.id+" "+b.name+" "+b.author+" "+b.publisher+" "+b.quantity); } } }

输出：