Java 数据结构包 - 链表实现-柚子小站

看了数组, 自然就想到用链表了. 说到这里我想起来刀魂里的Ivy, 一把剑鞭, 剑就像数组连在一起. 而链表就打散了连续在一起的内存地址. 看来修炼完数据结构与算法之后, 可以左手一把精钢哈希表盾牌, 右手一条链表数组剑鞭, 可以去刷怪(题)了.

LinkedBag设计
编写add方法
toArray方法
其他与遍历数组相关的方法
remove系列方法
链表实现包的优缺点

LinkedBag设计

LinkedBag首先要有一个东西当成节点, 肯定是一个Node类了. 但是这个类放在哪里, 有讲究. 由于无需将内部结构暴露给外边, 所以使用私有非静态内部类, 这样这个内部类的对象一定要附着在已经存在的外部对象, 而且还无法访问. 同时内部类又可以使用外部类的数据和泛型, 比较方便. 所以先创建一个实现了BagInterface的LinkedBag, 然后编排一个内部类:

public class LinkedBag<T> implements BagInterface<T> {

    private class Node {
        private T data;
        private Node next;

        private Node(T dataPortion) {
            this(dataPortion, null);
        }

        private Node(T dataPortion, Node nextNode) {
            this.data = dataPortion;
            this.next = nextNode;
        }
    }

    @Override
    public int getCurrentSize() {
        return 0;
    }

    @Override
    public boolean isEmpty() {
        return false;
    }

    @Override
    public boolean add(T newEntry) {
        return false;
    }

    @Override
    public T remove() {
        return null;
    }

    @Override
    public boolean remove(T anEntry) {
        return false;
    }

    @Override
    public void clear() {

    }

    @Override
    public int getFrequencyOf(T anEntry) {
        return 0;
    }

    @Override
    public boolean contains(T anEntry) {
        return false;
    }

    @Override
    public T[] toArray() {
        return null;
    }
}

这个玩意在学C的时候就知道用struct也是这个套路, 包含一个数据对象和一个指向自己结构的指针. Java里其实也是一样的. 不过面向对象的好处就是有构造器比较方便的使用. 两个构造器, 一个对应创建一个独立的新节点(或者说链表头部), 一个创建一个带有下一个节点的节点. 有了这个节点, 之后就可以来写一下LinkedBag的构造方法, LinkedBag中必须有一个Node对象, 用来指向一个链表的第一个节点:

public class LinkedBag<T> implements BagInterface<T> {

    private Node firstNode;
    private int numberOfEntries;

    public LinkedBag() {
        firstNode = null;
        numberOfEntries = 0;
    }

    //内部类定义和其他接口方法

}

这里定义了两个变量, 一个是指向第一个节点的firstNode引用, 一个是记录链表长度的值. 这里没有为了安全起见设置初始化的initialized布尔变量, 因为LinkedBag的初始化仅仅只是两个赋值, 而且都是默认值. 不涉及创建数组等数据结构. 因此不用担心, 之后的

编写add方法

链表添加一个节点的操作, 如果是从头添加, 其实是一样的, 根本无需考虑第一个节点是不是为空, 只需要如下步骤:

创建一个新节点newNode
将newNode的next指向firstNode
将firstNode指向newNode

根据这个方法, 就可以编制一个add方法, 这个也是一个核心方法.

/**
 * 向链表中添加一个新的数据, 原理是创建一个新节点, 让新节点指向链表头, 然后让链表头指向新节点
 * @param newEntry  The object to be added as a new entry.
 * @return 必定返回true, 如果因为内存用光, 无需从内存错误中恢复
 */
@Override
public boolean add(T newEntry) {
    Node newNode = new Node(newEntry);
    newNode.next = firstNode;
    firstNode = newNode;
    numberOfEntries++;
    return true;
}

这个方法永远返回true, 因为一般无需从内存耗尽错误中恢复.

toArray方法

这个方法其实核心就是遍历. 遍历链表的方法也很简单, 为了保险起见, 可以同时测试某个节点的.next为空和超出索引两个条件, 以免会造成不一致.

@Override
@SuppressWarnings("unchecked")
public T[] toArray() {
    T[] result = (T[]) new Object[numberOfEntries];
    int i = 0;
    Node currentNode = firstNode;
    while (i < numberOfEntries && currentNode != null){
        result[i++] = currentNode.data;
        currentNode = currentNode.next;
    }
    return result;
}

这段代码也是标配了, 基本上都会背了. 这里要注意的时候, 似乎没有必要去同时测试两个条件, 比如如果我们其他的操作都能够保证链表的结尾节点一定是null, 而每次add的时候numberOfEntries也会更新就可以. 同时测试两个值的话, 可以更高的程度上保持一致性. 此时有了numberOfEntries变量, 也可以把其他的方法都实现上了.

@Override
public int getCurrentSize() {
    return numberOfEntries;
}

@Override
public boolean isEmpty() {
    return numberOfEntries == 0 && firstNode == null;
}

这里的测试也同时测试了数量为0和首节点为null, 也是一个双重保证.

其他与遍历数组相关的方法

首先是getFrequencyof(), 知道了如何遍历, 就比较简单了:

@Override
public int getFrequencyOf(T anEntry) {
    int count = 0;
    int index = 0;
    Node currentNode = firstNode;

    while (currentNode != null && (index < numberOfEntries)) {
        if (anEntry.equals(currentNode.data)) {
            count++;
        }
        currentNode = currentNode.next;
        index++;
    }
    return count;
}

这个方法很简单,遍历链表, 相同就增加一个计数,最后返回计数. contains比这个简单粗暴一些, 不用遍历完, 只要发现就返回:

@Override
public boolean contains(T anEntry) {
    boolean found = false;
    int index = 0;
    Node currentNode = firstNode;
    while (currentNode != null && (index < numberOfEntries)) {
        if (anEntry.equals(currentNode.data)) {
            found = true;
            break;
        }
        currentNode = currentNode.next;
        index++;
    }
    return found;
}

这些套路都很熟悉了, 来看看删除.

remove系列方法

首先看看不加参数的删除. 从前边的遍历可以发现, 不像数组可以直接通过index来删除某个位置的元素. 既然如此, 我们就采取最简单的方法, 就是删除链表最后添加进去, 也就是第一个元素. 删除第一个元素的方法也很简单, 就是将firstNode直接指向firstNode的next即可, 这样中间的元素失去引用,就被删除在链子之外. 然后将数量减1.

@Override
public T remove() {
    T result = null;
    if (!isEmpty()) {
        result = firstNode.data;
        firstNode = firstNode.next;
        numberOfEntries--;
    }
    return null;
}

这个套路也是熟悉的不行. 然后来看删除指定的元素. 删除指定的元素首先就是要定位到那个元素. 其次, 就是要获取这个元素的上一个节点, 将上一个节点指向这个元素的下一个节点. 链表为空的时候当然就返回false. 这里的关键就是查找要稍微改变一下, 即找到那个元素的同时, 要获取那个元素的上一个节点. 但其实这种思路有点过时, 更好的方法是, 先找到要删除的节点, 然后用第一个节点中的数据直接替换掉要删除的节点, 然后将第一个节点删除. 即使只有一个节点也没有关系, 用自己替换自己, 然后会干掉自己. 这样就不用实际来移动被删除节点的前后节点. 只需要进行几个判断即可. 为了获取一个节点的引用, 可以来编写一个私有方法:

private Node getRefference(T entry) {
    int index = 0;
    Node currentNode = firstNode;
    while (currentNode != null && (index < numberOfEntries)) {
        if (entry.equals(currentNode.data)) {
            break;
        }
        currentNode = currentNode.next;
    }
    return currentNode;
}

然后使用这个方法, 加上一些判断, 就可以来写出删除一个Entry的remove方法:

@Override
public boolean remove(T anEntry) {
    boolean result = false;
    //表不为空
    if (!isEmpty()) {
        //获取节点引用
        Node target = getRefference(anEntry);
        //如果有该节点再进行删除操作
        if (target != null) {
            target.data = firstNode.data;
            remove();
            result = true;
        }
    }
    return result;
}

仔细思考的话这方法确实比拿到上一个节点的链接逻辑要好很多. 而且只需要遍历一次, 一样的复杂度, 但是逻辑确实好了一些. 有了这个私有方法之后, contains方法也可以使用这个私有方法, 有了可重用的私有方法, 方法的耦合程度就进一步下降了, 也更好修改了:

@Override
public boolean contains(T anEntry) {
    return getRefference(anEntry) != null;
}

到现在为止就实现完了全部接口里的方法.

链表实现包的优缺点

所谓优缺点, 肯定就是和数组相比较的优缺点, 来简单看一下:

添加一个项目, 固定在链表头部插入. 数组固定在末尾插入,不考虑变长的话, 都是常数操作. 如果要考虑变长, 则数组添加一个东西可能会遍历一遍, 因此数组的性能受是否定长影响.
删除一项, 链表固定删除第一项, 数组删除最后一项, 也是常数操作. 涉及到长度变化, 则会加上遍历的时间.
查找和删除, 都需要遍历, 二者是相等的.
在内存耗费上, 数组可能会有浪费的空间, 不过链表不会, 但代价就是链表还要存储额外的引用.

从整体上看, 除了内存使用更有效率之外, 二者本质上都是线性表, 所以在添加和删除上的时间差不多. 但是定长数组的时间可能会额外增加一个遍历也就是O(n)的时间, 特别要注意. 剩下就是继续写练习了.