最简单的动态数据结构 - 链表

链表是什么?

上几篇文章中,分别介绍了动态数组,栈和队列,其中都是通过resize的方法进行动态扩容,从而实现了动态的数据结构,不过这种方法称为伪动态。真正的动态数据结构还要从链表说起,链表是真正的动态数据结构,一个真正的动态数据结构不需要处理固定容量的问题。学好链表很重要,对后面复杂的数据结构是一种铺垫。链表见名知意,元素和元素之间就像链子一样拴住,元素也可以成为节点(Node),叫啥都行,反正能理解就好。每一个元素有两部分组成,一部分是元素本身,另一部分是下一个元素的引用。下文将元素本身就叫e,他的下一个引用就叫做next。

class Node
{
    E e; //当前元素本身
    Node next; //下一个元素的引用
}


上图表示,第一个元素的e是1,他的next是2。第二个元素的e是2,他的next是3。最后一个元素的e是3,但next为null,因为3就是最后一个元素,可以说如果一个元素的next为null,就代表他是最后一个元素。如果我想找到2,那就通过1去找,如果我想找到3,那不好意思,你也得通过1去找,因为1和3之间没有直接的关联,只能先通过1先找到2,2里面有存储3的地址。这也代表链表没有随机访问的能力,比如数组可以通过索引去找,效率很高。链表想找一个元素只能从头到尾遍历去找,查询效率低。

链表的实现

首先创建了一个Node内部类,目的是只给LinkedList外部类用,外面的类是不可以操作Node对象的,这样做是比较安全的。成员变量分别是E e和Node next,e用于存储元素本身,next存储下一个元素的引用。LinkedList里面维护了两个变量,Node head和size,head用于存储目前链表的头元素,size用于维护链表里元素的个数。

public class LinkedList {
    //内部维护一个Node对象,给外部类(LinkedList)使用
    private class Node {
        public E e; //当前Node对象的元素值
        public Node next; //当前Node对象下一个对象的引用
        public Node(E e,Node next) {
            this.e = e;
            this.next = next;
        }
        public Node(E e) {
            this.e = e;
            this.next = null;
        }
        public Node() {
            this.e = null;
            this.next = null;
        }
    }

    //头元素节点
    private Node head;
        //当前链表节点个数
    private int size;
    public LinkedList() {
        head = null;
        size = 0;
    }
    public int getSize() {
        return size;
    }
    public boolean isEmpty() {
        return size == 0;
    }
}

添加一个头节点

添加头节点就是要创建一个新Node节点,新节点的e为666,新节点的next就指向了原来的头节点,改变指向后,要维护一下head,让新创建的这个节点变成头节点。最后维护一下size的个数。

public void addFirst(E e)
{
    Node node = new Node(e); //创建一个节点
    node.next = head; //节点的next为当前头节点
    head = node; //改变head指向,现在头的位置变成了最新的node
    //head = new Node(e,head); 以上三步可简化成这种写法
    size++;
}

按照索引位置添加元素

现在要把新元素添加到指定位置,比如索引为2的位置插入一个新元素。那就要找到索引2之前的那个元素,因为新元素插入后,要维护一下指向关系,原来是1的next为2,现在666的next变成了2,1的next为666。找到了1之后,先把1的next给666,让666的next先指向2,然后1的next在指向666就好啦。看下面图或者自己画一下就很清楚了。可是怎么能找到索引为1的元素呢?遍历!我们可以维护一个变量,用于保存每次next的值,可以看到从头元素到1的位置只需要一次next。

public void addByIndex(E e,int index) //index = 2
{
    if(index < 0 || index > size)
        throw new IllegalArgumentException("Add failed. Because index is illegal.");
    if(index == 0)
        addFirst(e);
    //1.要想得到某个位置的元素,需要从第一个往后找,因为第一个存储的是第二个的"联系方式",第二个存储的是第三个人的"联系方式"。
    //这里循环只是遍历多少次才能拿到索引前的那个元素,里面的x变量没有任何使用意义。你也可以写成x = 1; x < index; 只要是循环次数算对了就行。
    //0 1 2 3 , 如果index = 2,那么待插入元素就是这样 0 1 _ 2 3 ,那么从头元素开始遍历,拿到索引为1的节点,只需要经过一次next
    Node prevNode = head;
    for(int x = 0; x < index - 1; x++) {
        head = prevNode.next;
    }
    //2.拿到currentNode后,维护指向关系
    Node node = new Node(e);
    node.next = prevNode.next;
    prevNode.next = node;
    //currentNode.next = new Node(node,currentNode.next);//简略写法
    size++;
}

虚拟节点的引入

实现上面的addByIndex方法时,需要对index为0时,做特殊判断处理。那能不能不做特殊判断,改变一种思想,让addFirst方法也能复用呢?办法是使用虚拟节点。设计一个dummyHead,每次在第0个位置添加元素时候,都可以通过dummyHead找到原来的头元素位置。然后按索引添加的逻辑就可以复用了。

private Node dummyHead;
private int size;
public LinkedList() {
    dummyHead = new Node(null, null); //创建虚拟节点
    size = 0;
}
//链表头添加元素
public void addFirst(E e) {
    addByIndex(e, 0);
}
//链表尾添加元素
public void addLast(E e) {
    addByIndex(e, size);
}
public void addByIndex(E e, int index) //3
{
    if (index < 0 || index > size)
        throw new IllegalArgumentException("Add failed. Because index is illegal.");
    //如果index为3,那么从dummyHead到索引2的位置,一共要三次next。循环从0开始,然后<3,也就是0 1 2一共三次
    Node currentNode = dummyHead; //从头元素开始遍历  dummy 0  1  2 -- 3
    for (int x = 0; x < index; x++) {
        dummyHead = currentNode.next;
    }
    Node node = new Node(e);
    node.next = currentNode.next;
    currentNode.next = node;
    //currentNode.next = new Node(node,currentNode.next);//简略写法
    size++;
}

在提供一些基础的方法,比如查询,删除,是否包含某个元素,修改某个元素。只要掌握了遍历链表的思想,其实万变不离其宗。要注意的就是控制好索引的边界。

public E get(int index) {
    if (index < 0 || index >= size)
        throw new IllegalArgumentException("Get filed.Index is not true!");
    Node currentNode = dummyHead;
    for (int x = 0; x < index; x++) {
        currentNode = currentNode.next;
    }
    return (E) currentNode.next.e;
}

public E getFirst()
{
    return get(0);
}

public E getLast()
{
    return get(size - 1);
}

public void set(E e,int index)
{
    if (index < 0 || index >= size)
        throw new IllegalArgumentException("Get filed.Index is not true!");
    Node currentNode = dummyHead;
    for(int x = 0; x < index; x++) {
        currentNode = currentNode.next;
    }
    currentNode.next.e = e;
}

public boolean contains(E e)
{
    Node currentNode = dummyHead;
    for(int x = 0; x < size; x++)
    {
        currentNode = currentNode.next;
        if(currentNode.e.equals(e))
        {
            return true;
        }
    }
    return false;
}

@Override
public String toString() {
    StringBuffer sb = new StringBuffer();
    sb.append("linkedHead[");
    Node currentNode = dummyHead;
    for(int x = 1; x <= size; x++)
    {
        currentNode = currentNode.next;
        sb.append(currentNode.e + "....");
    }
    sb.append("]linkedFooter");
    return sb.toString();
}

删除操作

//删除链表中的某个元素
public E delete(int index)
{
    Node currentNode = dummyHead;
    for(int x = 0; x < index; x++) {
        currentNode = currentNode.next;
    }
    
    Node delNode = currentNode.next;
    currentNode.next = delNode.next;
    delNode.next = null;
    size--;
    return (E) delNode.e;
}

你可能感兴趣的