java - 如何用Java实现我自己的LinkedList数据结构？

Question

我正在做一些事情，如果我使用的几个对象是由我编写的(而不是使用 Java 的库)，那么事情会变得更容易。我目前正致力于实现 ArrayList<ArrayList>使用我的 MyHashTable 对象(我们可以称之为 LinkedList )类(class)和我的Node类(class)。这是我正确实现的 LinkedList到目前为止的类(class):

public class LinkedList{
    Node start;
    int length;

    public LinkedList(){
        start = new Node();
        length= 0;
    }

    public void addNode(Node node){
        Node s= start;
        while (s.next != null){
            s= s.next;
        }
        s.next= node;
        length++;
    }

    public int getLength(){
        return length;
    }

    public boolean findNode(Node node){
        Node s= start;
        while(s.next != null){
            if (s == node){
                return true;
            }
            s.next= node;
        }
        return false;
    }

}

所以我在修改此类以接受 Java 泛型时遇到了麻烦(这样我就可以创建一个链表的链表，而不是简单的节点链表)。让我知道我是否应该提供我的Node类看起来。

Answer 1

通用 LinkedList 只是替换值的类型。您没有显示您的 Node 类，所以我不明白您如何使用它。这是一个通用的链表:

class LinkedList<E> {
    static class Node<E> {
        E value;
        Node<E> next;

        Node(E value) {
            this.value = value;
        }
    }

    Node<E> head = new Node<E>(null);
    Node<E> tail = head;
    int size;

    void add(E value) {
        tail = tail.next = new Node<E>(value);
        size++;
    }

    E get(int index) {
        if(index < 0 || size <= index)
            throw new OutOfBoundsException(index);

        Node<E> node = head.next;
        while(index > 0) {
            node = node.next;
            index--;
        }

        return node.value;
    }
}

但我不确定你所说的将其放入 ArrayList 是什么意思。 ArrayList 完全不同，它是一个自动调整自身大小的数组:

class ArrayList<E> {
    Object[] array = new Object[10];
    int size;

    void add(E value) {
        if(size >= array.length) {
            array = Arrays.copyOf(array, (int)(size * 3L / 2L));
        }

        array[size++] = value;
    }

    E get(int index) {
        return (E)array[index];
    }
}

虽然我认为您可以使用多维数组来组合哈希表，但我不推荐这样做。您不能直接实例化一个包含 2^32 个元素的数组，这意味着您必须管理交集。我不明白 ArrayList 如何成为一个有效的哈希表。这是一个类似于 Java 的简单哈希表实现。该表是一个链表数组。

class HashTable<K, V> {
    static class Entry<K, V> {
        K key;
        V value;

        Entry<K, V> next;

        Entry(K key, V value) {
           this.key = key;
           this.value = value;
        }
    }

    Entry[] table = new Entry[8];
    int size;

    void put(K key, V value) {
        Entry<K, V> entry = table[indexFor(key)];
        while(entry != null) {
            if(entry.key.equals(key)) {
                entry.value = value;
                return;
            }

            entry = entry.next;
        }

        resizeIfNeeded();

        addEntry(new Entry<K, V>(key, value));
        size++;
    }

    void addEntry(Entry<K, V> newEntry) {
        int index = indexFor(newEntry.key);
        Entry<K, V> entry = table[index];

        if(entry == null) {
            table[index] = newEntry;

        } else {
            while(entry.next != null)
                entry = entry.next;

            entry.next = newEntry;
        }
    }

    void resizeIfNeeded() {
        if(size < table.length)
            return;

        Entry[] old = table;
        table = new Entry[old.length << 1];

        for(Entry<K, V> entry : old) {
            while(entry != null) {
                addEntry(entry);
                Entry<K, V> next = entry.next;
                entry.next = null;
                entry = next;
            }
        }
    }

    V get(K key) {
        Entry<K, V> entry = table[indexFor(key)];
        while(entry != null) {
            if(entry.key.equals(key))
                return entry.value;

            entry = entry.next;
        }

        return null;
    }

    int indexFor(K key) {
        return key.hashCode() & table.length - 1;
    }
}

正如我在评论中提到的，这听起来像 XY problem 。我不明白这比使用 Java 数据结构更容易。也许您有不同的问题要问。