数据结构篇02、链表

本文实现的LinkedList，底层核心原理与java工具库中的LinkedList类似，不过在java工具库中的LinkedList使用的是双向链表，我们实现的这个是单向链表；

1、Node节点类、构造方法与常规函数

如下所示，Node节点类包含元素e和next节点，元素e用于保存数据，使用的是泛型；next节点指向下一个Node节点元素，这也是称之为链表的原因；

两个成员属性dummyHead和size，dummyHead表示虚拟头节点，其指向的下一个元素才是真正的头节点；size表示元素个数；

无参的构造函数就是将虚拟头节点初始化，size置为0；

getSize函数返回链表元素个数；isEmpty函数返回链表是否为空；

public class LinkedList<E> {

	//Node节点类
    private class Node{
        public E e;
        public Node next;

        public Node(E e, Node next){
            this.e = e;
            this.next = next;
        }

        public Node(E e){
            this(e, null);
        }

        public Node(){
            this(null, null);
        }

        @Override
        public String toString(){
            return e.toString();
        }
    }

    //虚拟头节点
    private Node dummyHead;
    private int size;

    public LinkedList(){
        dummyHead = new Node();
        size = 0;
    }

    // 获取链表中的元素个数
    public int getSize(){
        return size;
    }

    // 返回链表是否为空
    public boolean isEmpty(){
        return size == 0;
    }
    、、、
}
复制代码

2、往链表中添加元素

add(int index, E e)函数表示往索引index处添加元素e；其实在链表中一般没有这种需求，我们只是练习用；首先通过一个for循环找到index索引的节点，然后new一个节点插入进去即可；时间复杂度为O(n);

addFirst表示往链表头添加元素，因此时间复杂度为O(1);

addLast表示往链表尾添加元素，因此时间复杂度为O(n);这里注意一下，java的util库中LinkedList往链表尾添加元素的时间复杂度为O(1),因为它是维护了一个双向链表，头节点和尾节点都有记录，直接从尾节点插入一个元素即可，并不需要循环遍历，因此为O(1)的时间复杂度；

// 在链表的index(0-based)位置添加新的元素e
public void add(int index, E e){

    if(index < 0 || index > size)
        throw new IllegalArgumentException("Add failed. Illegal index.");

    Node prev = dummyHead;
    for(int i = 0 ; i < index ; i ++)
        prev = prev.next;

    prev.next = new Node(e, prev.next);
    size ++;
}

// 在链表头添加新的元素e
public void addFirst(E e){
    add(0, e);
}

// 在链表末尾添加新的元素e
public void addLast(E e){
    add(size, e);
}
复制代码

3、获取链表中的元素

get(int index)表示获取index索引处的元素，跟添加元素类似，也是通过一个for循环找到index位置的节点，然后返回节点中的元素即可；时间复杂度为O(n);

getFirst()表示获取链表头元素，同理也是O(1)时间复杂度；

getLast()表示获取链表尾元素，同理也是O(n)时间复杂度；

// 获得链表的第index(0-based)个位置的元素
// 在链表中不是一个常用的操作
public E get(int index){

    if(index < 0 || index >= size)
        throw new IllegalArgumentException("Get failed. Illegal index.");

    Node cur = dummyHead.next;
    for(int i = 0 ; i < index ; i ++)
        cur = cur.next;
    return cur.e;
}

// 获得链表的第一个元素
public E getFirst(){
    return get(0);
}

// 获得链表的最后一个元素
public E getLast(){
    return get(size - 1);
}
复制代码

4、修改和查找元素

set(int index, E e)表示修改index索引处的元素为e；同理也是通过一个for循环找到index索引对应的Node节点，然后修改元素值即可；

contains(E e)返回链表是否存在元素e，通过一个while循环在链表中遍历节点，找到返回true，遍历完仍没找到返回false；

// 修改链表的第index(0-based)个位置的元素为e
// 在链表中不是一个常用的操作
public void set(int index, E e){
    if(index < 0 || index >= size)
        throw new IllegalArgumentException("Set failed. Illegal index.");

    Node cur = dummyHead.next;
    for(int i = 0 ; i < index ; i ++)
        cur = cur.next;
    cur.e = e;
}

// 查找链表中是否有元素e
public boolean contains(E e){
    Node cur = dummyHead.next;
    while(cur != null){
        if(cur.e.equals(e))
            return true;
        cur = cur.next;
    }
    return false;
}
复制代码

5、从链表中删除元素

remove(int index)表示删除index索引处的节点，首先通过一个for循环找到待删除节点，然后将待删除节点的前一个节点的后一个节点指向待删除节点的后一个节点，这样即可删除节点；最后将删除节点的下一个节点指向null，便于垃圾回收；

removeFirst()表示删除链表头节点，时间复杂度为O(1);

removeLast()表示删除链表尾节点，时间复杂度为O(n);

removeElement(E e)表示删除元素e对应的节点，跟查找结点一样，首先通过while循环找到此节点，然后跟remove函数一样操作即可删除节点；

// 从链表中删除index(0-based)位置的元素, 返回删除的元素
// 在链表中不是一个常用的操作
public E remove(int index){
    if(index < 0 || index >= size)
        throw new IllegalArgumentException("Remove failed. Index is illegal.");

    Node prev = dummyHead;
    for(int i = 0 ; i < index ; i ++)
        prev = prev.next;

    Node deleteNode = prev.next;
    prev.next = deleteNode.next;
    deleteNode.next = null;
    size --;

    return deleteNode.e;
}

// 从链表中删除第一个元素, 返回删除的元素
public E removeFirst(){
    return remove(0);
}

// 从链表中删除最后一个元素, 返回删除的元素
public E removeLast(){
    return remove(size - 1);
}

// 从链表中删除元素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){
        Node delNode = prev.next;
        prev.next = delNode.next;
        delNode.next = null;
        size --;
    }
}
复制代码

6、toString函数打印链表

重写toString函数用于查看链表信息；

我们通过StringBuilder依次拼接链表节点值，最后转换为String返回；

@Override
public String toString(){
    StringBuilder res = new StringBuilder();

    Node cur = dummyHead.next;
    while(cur != null){
        res.append(cur + "->");
        cur = cur.next;
    }
    res.append("NULL");

    return res.toString();
}
复制代码

7、LinkedList完整代码如下

public class LinkedList<E> {

    private class Node{
        public E e;
        public Node next;

        public Node(E e, Node next){
            this.e = e;
            this.next = next;
        }

        public Node(E e){
            this(e, null);
        }

        public Node(){
            this(null, null);
        }

        @Override
        public String toString(){
            return e.toString();
        }
    }

    private Node dummyHead;
    private int size;

    public LinkedList(){
        dummyHead = new Node();
        size = 0;
    }

    // 获取链表中的元素个数
    public int getSize(){
        return size;
    }

    // 返回链表是否为空
    public boolean isEmpty(){
        return size == 0;
    }

    // 在链表的index(0-based)位置添加新的元素e
    // 在链表中不是一个常用的操作
    public void add(int index, E e){

        if(index < 0 || index > size)
            throw new IllegalArgumentException("Add failed. Illegal index.");

        Node prev = dummyHead;
        for(int i = 0 ; i < index ; i ++)
            prev = prev.next;

        prev.next = new Node(e, prev.next);
        size ++;
    }

    // 在链表头添加新的元素e
    public void addFirst(E e){
        add(0, e);
    }

    // 在链表末尾添加新的元素e
    public void addLast(E e){
        add(size, e);
    }

    // 获得链表的第index(0-based)个位置的元素
    // 在链表中不是一个常用的操作
    public E get(int index){

        if(index < 0 || index >= size)
            throw new IllegalArgumentException("Get failed. Illegal index.");

        Node cur = dummyHead.next;
        for(int i = 0 ; i < index ; i ++)
            cur = cur.next;
        return cur.e;
    }

    // 获得链表的第一个元素
    public E getFirst(){
        return get(0);
    }

    // 获得链表的最后一个元素
    public E getLast(){
        return get(size - 1);
    }

    // 修改链表的第index(0-based)个位置的元素为e
    // 在链表中不是一个常用的操作
    public void set(int index, E e){
        if(index < 0 || index >= size)
            throw new IllegalArgumentException("Set failed. Illegal index.");

        Node cur = dummyHead.next;
        for(int i = 0 ; i < index ; i ++)
            cur = cur.next;
        cur.e = e;
    }

    // 查找链表中是否有元素e
    public boolean contains(E e){
        Node cur = dummyHead.next;
        while(cur != null){
            if(cur.e.equals(e))
                return true;
            cur = cur.next;
        }
        return false;
    }

    // 从链表中删除index(0-based)位置的元素, 返回删除的元素
    // 在链表中不是一个常用的操作
    public E remove(int index){
        if(index < 0 || index >= size)
            throw new IllegalArgumentException("Remove failed. Index is illegal.");

        Node prev = dummyHead;
        for(int i = 0 ; i < index ; i ++)
            prev = prev.next;

        Node deleteNode = prev.next;
        prev.next = deleteNode.next;
        deleteNode.next = null;
        size --;

        return deleteNode.e;
    }

    // 从链表中删除第一个元素, 返回删除的元素
    public E removeFirst(){
        return remove(0);
    }

    // 从链表中删除最后一个元素, 返回删除的元素
    public E removeLast(){
        return remove(size - 1);
    }

    // 从链表中删除元素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){
            Node delNode = prev.next;
            prev.next = delNode.next;
            delNode.next = null;
            size --;
        }
    }

    @Override
    public String toString(){
        StringBuilder res = new StringBuilder();

        Node cur = dummyHead.next;
        while(cur != null){
            res.append(cur + "->");
            cur = cur.next;
        }
        res.append("NULL");

        return res.toString();
    }
}
复制代码