简介
双向链表也叫双向表，是链表的一种，它由多个结点组成，每个结点都由一个数据域和两个指针域组成，数据域用 来存储数据，其中一个指针域用来指向其后继结点，另一个指针域用来指向前驱结点。链表的头结点的数据域不存储数据，指向前驱结点的指针域值为null，指向后继结点的指针域指向第一个真正存储数据的结点。
java实现：
/**
* 双向链表
* @author wen.jie
* @date 2021/8/6 14:10
*/
public class DoublyLinkedList<T> implements Iterable<T>{
//头节点
protected Node<T> head;
//尾节点
protected Node<T> last;
//长度
int size = 0;
protected static class Node<T> {
protected T item;
protected Node<T> pre;
protected Node<T> next;
public Node (T item, Node<T> pre, Node<T> next){
this.item = item;
this.pre = pre;
this.next = next;
}
}
public DoublyLinkedList() {
this.head = new Node<>(null, null, null);
this.last = null;
}
public void clear(){
this.head.next = null;
this.last = null;
this.size = 0;
}
public int size(){
return size;
}
public T getFirst(){
if(isEmpty()){
return null;
}
return this.head.next.item;
}
public T getLast(){
if(isEmpty()){
return null;
}
return this.last.item;
}
protected void putLast(T t){
Node<T> node = new Node<>(t, last, null);
this.last.next = node;
this.last = node;
}
/**
* 把节点t插入到pre和last之间
* @author wen.jie
* @date 2021/8/9 22:30
*/
protected void insert(T t, Node<T> pre, Node<T> last) {
Node<T> tNode = new Node<>(t, pre, last);
pre.next = tNode;
last.pre = tNode;
}
public void add(T t){
if (isEmpty()){
Node<T> node = new Node<>(t, head, null);
head.next = node;
last = node;
}else {
putLast(t);
}
size++;
}
/**
* 指定位置处插入元素
* @author wen.jie
* @date 2021/8/6 14:41
*/
public void add(int i, T t) {
Node<T> pre = head;
for(int index = 0; index< i; index++){
pre = pre.next;
}
insert(t, pre, pre.next);
size++;
}
/**
* 获取指定位置i处的元素
* @author wen.jie
* @date 2021/8/6 14:48
*/
public T get(int i) {
Node<T> n = head.next;
for(int index = 0; index< i; index++){
n = n.next;
}
return n.item;
}
/**
* 元素T在链表第一次出现的位置
* @author wen.jie
* @date 2021/8/6 14:48
*/
public int indexOf(T t) {
Node<T> n = head.next;
for(int i = 0; n.next!=null; i++){
n = n.next;
if(Objects.equals(t, n))
return i;
}
return -1;
}
/**
* 删除指定i位置处的元素
* @author wen.jie
* @date 2021/8/6 14:50
*/
public T remove(int i){
Node<T> pre = head;
for(int index = 0; index < i; index++){
pre = pre.next;
}
Node<T> curr = pre.next;
Node<T> tNode = curr.next;
pre.next = tNode;
tNode.pre = pre;
size--;
return curr.item;
}
public boolean isEmpty(){
return size == 0;
}
@Override
public Iterator<T> iterator() {
return new Itr();
}
private class Itr implements Iterator<T> {
private Node<T> n;
public Itr(){
this.n = head;
}
@Override
public boolean hasNext() {
return n.next != null;
}
@Override
public T next() {
n = n.next;
return n.item;
}
}
}
测试：
@Test
public void test(){
DoublyLinkedList<String> list = new DoublyLinkedList<>();
list.add("a");
list.add("b");
list.add("c");
for (String str : list) {
System.out.println(str);
}
System.out.println("~~~~~~~~~~~~~~~~~~~");
System.out.println(list.get(1));
list.remove(1);
System.out.println(list.size());
System.out.println(list.getFirst());
list.remove(0);
System.out.println(list.getFirst());
System.out.println(list.size());
}
链表复杂度分析
get(int i):每一次查询，都需要从链表的头部开始，依次向后查找，随着数据元素N的增多，比较的元素越多，时间复杂度为O(n)
insert(int i,T t):每一次插入，需要先找到i位置的前一个元素，然后完成插入操作，随着数据元素N的增多，查找的元素越多，时间复杂度为O(n)
remove(int i):每一次移除，需要先找到i位置的前一个元素，然后完成插入操作，随着数据元素N的增多，查找的元素越多，时间复杂度为O(n)
相比较顺序表，链表插入和删除的时间复杂度虽然一样，但仍然有很大的优势，因为链表的物理地址是不连续的， 它不需要预先指定存储空间大小，或者在存储过程中涉及到扩容等操作，同时它并没有涉及的元素的交换。
相比较顺序表，链表的查询操作性能会比较低。因此，如果我们的程序中查询操作比较多，建议使用顺序表，增删操作比较多，建议使用链表。