下面是Java实现自定义LinkedList类的攻略:
1. LinkedList类的概述
LinkedList是Java API中提供的一种线性数据结构,实现了List和Deque接口,底层使用双向链表实现。LinkedList的特点是支持插入和删除操作,但查找操作比较慢。对于需要频繁增删元素而不需要随机访问的场景,使用LinkedList比较合适。
2. 自定义LinkedList类的实现
Java中提供的LinkedList类已经比较完善,但我们还是可以模仿它的实现,自己编写一个自定义的LinkedList类。以下是自定义LinkedList类的示例代码:
public class MyLinkedList<E> {
private Node<E> head;
private int size;
private static class Node<E> {
E data;
Node<E> prev;
Node<E> next;
Node(E element, Node<E> prev, Node<E> next) {
this.data = element;
this.prev = prev;
this.next = next;
}
}
public MyLinkedList() {
head = new Node<>(null, null, null);
head.prev = head;
head.next = head;
size = 0;
}
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
public void add(E element) {
add(size, element);
}
public void add(int index, E element) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException();
}
Node<E> newNode = new Node<>(element, null, null);
Node<E> p = head;
for (int i = 0; i < index; i++) {
p = p.next;
}
newNode.prev = p;
newNode.next = p.next;
p.next.prev = newNode;
p.next = newNode;
size++;
}
public E remove(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
Node<E> p = head;
for (int i = 0; i < index; i++) {
p = p.next;
}
E element = p.next.data;
p.next.next.prev = p;
p.next = p.next.next;
size--;
return element;
}
public E get(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
Node<E> p = head.next;
for (int i = 0; i < index; i++) {
p = p.next;
}
return p.data;
}
}
3. 具体说明
自定义LinkedList类包含一个内部类Node,表示双向链表中的一个节点,其中data表示节点的数据,prev和next表示节点的前驱和后继。头节点head的data值为null,prev和next均指向自身,表示空链表。size表示链表中元素的个数。
构造函数中初始化头节点head,并使其prev和next均指向自身。
size()方法返回链表中元素的个数。
isEmpty()方法判断链表是否为空。
add(E element)方法向链表末尾添加一个元素。
add(int index, E element)方法在指定位置添加一个元素。该方法先判断索引位置是否合法,然后依次找到要添加位置的前驱节点p,创建一个新节点newNode,并将newNode的前驱和后继指向p和p的后继节点,然后将p的后继节点的前驱指向newNode,p的后继指向newNode。
remove(int index)方法移除指定位置的元素。该方法先判断索引位置是否合法,然后依次找到要移除位置的前驱节点p,将要移除的元素保存下来,将p的后继节点的后继节点的前驱指向p,p的后继指向p的后继节点的后继节点。
get(int index)方法获取指定位置的元素。该方法先判断索引位置是否合法,然后依次找到指定位置的节点p,返回其data值。
4. 示例
MyLinkedList<String> list = new MyLinkedList<>();
list.add("a");
list.add("b");
list.add("c");
System.out.println(list.get(1)); // 输出 b
list.remove(0);
System.out.println(list.get(0)); // 输出 b
System.out.println(list.size()); // 输出 2
以上示例中,我们创建了一个自定义的LinkedList对象list,向其中添加了三个元素a、b、c,并输出了下标为1的元素b的结果。然后移除了下标为0的元素a,并输出了下标为0的元素b的结果,以及list的元素个数2。
本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:Java实现自定义LinkedList类的示例代码 - Python技术站