链表

2019-06-18 本文已影响0人代夫阿普曼

链表通过指针将零散的数据块连接在一起，这些内存块被称为节点（Node）。通常每个节点除了储存数据之外还记录下一个节点的地址。

//Node类是LinkedList类的内部类，泛型E定义在LinkedList上
class Node {
    E e;        //数据域
    Node next;  //下一个节点
    
    Node() {
        this(null, null);
    }
    
    Node(E e) {
        this(e, null);
    }
    
    Node(E e, Node next) {
        this.e = e;
        this.next = next;
    }
}

与数组相比，数组的存储空间是连续的。因此为了保证数组的存储空间的连续性，需要搬移节点。而链表的各个节点是由指针串联起来的，插入和删除时只需维护指针即可，这样的时间复杂度为O(1)。

单链表LinkedList

设置虚拟头结点（哨兵）方便实现统一的逻辑代码，哨兵节点不存储数据。无论链表是否为空，head指针都会指向它，作为链表的头结点始终存在。下面是LinkedList的两个成员变量

private Node dummyHead;     //哨兵
private int size;

//构造器初始化
public LinkedList() {
    dummyHead = new Node();
    size = 0;
}

链表的重要操作

add(int index, E e):在index位置插入元素e

public viod add(int index, E e) {
    Node prev = dummyHead;
    
    //指针移动到目标节点的前一个节点上
    for(int i = 0; i < index; i ++) {
        prev = prev.next;
    }
    
    //修改指针的指向
    //Node newNode = new Node(e);
    //newNode.next = prev.next;
    //prev.next = newNode;
    
    //上面的三行合并成一行
    prev.next = new Node(e, prev.next);
    
    size ++;
}

removeElement(E e)：移除指定的元素e

public void removeElement(E e) {
    Node prev = dummyHead;
    
    while(prev.next != null) {
        if(prev.next.e.equals(e)) {
            //在找到目标元素的前一个节点处停止
            break;
        }
        prev = prev.next;
    }
    if(prev.next != null) {
        prev.next = prev.next.next;
    }
}

remove(int index)：移除指定位置上的元素，并返回该元素

public E remove(int index) {
    Node prev = dummyHead;
    
    //在找到目标元素的前一个节点处停止
    for(int i = 0; i < index; i ++) {
        prev = prev.next;
    }
    
    //记录节点，用于返回
    Node retNode = prev.next;
    //修改指针
    prev.next = retNode.next;
    //销毁被删元素
    retNode.next = null;
   
    size --;
    
    return retNode.e;
}

链表

单链表LinkedList

链表的重要操作

猜你喜欢

热点阅读