JAVA链表设计

尼采般地抒情 2020-09-05 计算机素养数据结构与算法 📶线结构：字符串-数组-栈-队列 loading 次访问 loading

LinkedList和ArrayList的设计

同时设计LinkedList和ArrayList

LinkedList不需要构造函数
ArrayList需要，后者需要一个容量的初始化。

接口List设计

只用来声明对外接口，不能声明

package com.wztlink1013.ds.linkedlist;

/**

fun：实现ArrayList和LinkedList的接口

/

public interface List<E> {
    static final int ELEMENT_NOT_FOUND = -1;
/**
 * 元素的数量[抽象类中实现]
 * @return
 */
int size();

/**
 * 是否为空[抽象类中实现]
 * @return
 */
boolean isEmpty();

/**
 * 是否包含某个元素[抽象类中实现]
 * @param element
 * @return
 */
boolean contains(E element);

/**
 * 添加元素到尾部[抽象类中实现]
 * @param element
 */
void add(E element);

/**
 * 清除所有元素[实现类中实现]
 */
void clear();

/**
 * 获取index位置的元素[实现类中实现]
 * @param index
 * @return
 */
E get(int index);

/**
 * 设置index位置的元素[实现类中实现]
 * @param index
 * @param element
 * @return 原来的元素ֵ
 */
E set(int index, E element);

/**
 * 在index位置插入一个元素[实现类中实现]
 * @param index
 * @param element
 */
void add(int index, E element);

/**
 * 删除index位置的元素[实现类中实现]
 * @param index
 * @return
 */
E remove(int index);

/**
 * 查看元素的索引[实现类中实现]
 * @param element
 * @return
 */
int indexOf(E element);

}

抽象类AbstractList设计

放ArrayList和LinkedList的公共代码

实现List接口类的共同代码
ArrayList和LinkedList都用得到但是不对外公开的代码

声明抽象类abstract，就意味着可以不用全部实现接口List里面的所有方法

package com.wztlink1013.ds.linkedlist;

/**

fun：放ArrayList和LinkedList公共代码的抽象类（父类）

/

public abstract class AbstractList<E> implements List<E> {
protected int size;
/**
 * 元素的数量
 * @return
 */
public int size() {
    return size;
}

/**
 * 是否为空
 * @return
 */
public boolean isEmpty() {
    return size == 0;
}

/**
 * 是否包含某个元素
 * @param element
 * @return
 */
public boolean contains(E element) {
    return indexOf(element) != ELEMENT_NOT_FOUND;
}

/**
 * 添加元素到尾部
 * @param element
 */
public void add(E element) {
    add(size, element);
}

/**
 * 下面三个是ArrayList和LinkedList两个实现类中的公共代码
 * */
protected void outOfBounds(int index) {
    throw new IndexOutOfBoundsException(&quot;Index:&quot; + index + &quot;, Size:&quot; + size);
}

protected void rangeCheck(int index) {
    if (index &lt; 0 || index &gt;= size) {
        outOfBounds(index);
    }
}

protected void rangeCheckForAdd(int index) {
    if (index &lt; 0 || index &gt; size) {
        outOfBounds(index);
    }
}

}

ArrayList设计

package com.wztlink1013.ds.linkedlist;

/**
 *fun：实现动态数组
 */
@SuppressWarnings("unchecked")
public class ArrayList<E> extends AbstractList<E> {
    private E[] elements;
private static final int DEFAULT_CAPACITY = 10;

public ArrayList(int capaticy) {
    capaticy = (capaticy &lt; DEFAULT_CAPACITY) ? DEFAULT_CAPACITY : capaticy;
    elements = (E[]) new Object[capaticy];
}

public ArrayList() {
    this(DEFAULT_CAPACITY);
}


@Override
public void clear() {
    for (int i = 0; i &lt; size; i++) {
        elements[i] = null;
    }
    size = 0;
}

@Override
public E get(int index) {
    rangeCheck(index);
    return elements[index];
}

@Override
public E set(int index, E element) {
    rangeCheck(index);

    E old = elements[index];
    elements[index] = element;
    return old;
}

@Override
public void add(int index, E element) {
    rangeCheckForAdd(index);

    ensureCapacity(size + 1);

    for (int i = size; i &gt; index; i--) {
        elements[i] = elements[i - 1];
    }
    elements[index] = element;
    size++;
}

@Override
public E remove(int index) {
    rangeCheck(index);

    E old = elements[index];
    for (int i = index + 1; i &lt; size; i++) {
        elements[i - 1] = elements[i];
    }
    elements[--size] = null;
    return old;
}

@Override
public int indexOf(E element) {
    if (element == null) {  // 1
        for (int i = 0; i &lt; size; i++) {
            if (elements[i] == null) return i;
        }
    } else {
        for (int i = 0; i &lt; size; i++) {
            if (element.equals(elements[i])) return i; // n
        }
    }
    return ELEMENT_NOT_FOUND;
}


/**
 * 保证要有capacity的容量
 * @param capacity
 */
private void ensureCapacity(int capacity) {
    int oldCapacity = elements.length;
    if (oldCapacity &gt;= capacity) return;

    // 新容量为旧容量的1.5倍
    int newCapacity = oldCapacity + (oldCapacity &gt;&gt; 1);
    E[] newElements = (E[]) new Object[newCapacity];
    for (int i = 0; i &lt; size; i++) {
        newElements[i] = elements[i];
    }
    elements = newElements;

    System.out.println(oldCapacity + &quot;扩容为&quot; + newCapacity);
}

@Override
public String toString() {
    // size=3, [99, 88, 77]
    StringBuilder string = new StringBuilder();
    string.append(&quot;size=&quot;).append(size).append(&quot;, [&quot;);
    for (int i = 0; i &lt; size; i++) {
        if (i != 0) {
            string.append(&quot;, &quot;);
        }

        string.append(elements[i]);

    }
    string.append(&quot;]&quot;);
    return string.toString();
}

/**
 * 新添加功能
 */
public int search(E element){
    for (int i = 0;i&lt;size;i++){
        if (element == elements[i]){
            return i;
        }
    }
    return ELEMENT_NOT_FOUND;
}

}

LinkedList设计

package com.wztlink1013.ds.linkedlist;

/**
 *fun：链表的实现
 */
@SuppressWarnings("unchecked")
public class LinkedList<E> extends AbstractList<E> {
    private Node<E> first;
    private Node<E> last;
private static class Node&lt;E&gt; {
    E element;
    Node&lt;E&gt; prev;
    Node&lt;E&gt; next;
    public Node(E element, Node&lt;E&gt; next) {
        this.element = element;
        this.next = next;
    }
}

@Override
public void clear() {
    size = 0;
    first = null;
    last = null;
}

@Override
public E get(int index) {
    return node(index).element;
}

@Override
public E set(int index, E element) {
    Node&lt;E&gt; node = node(index);
    E old = node.element;
    node.element = element;
    return old;
}

@Override
public void add(int index, E element) {
    if (index == 0){
        first = new Node&lt;&gt;(element, first);
    } else {
        Node&lt;E&gt; prev = node(index - 1);
        prev.next = new Node&lt;&gt;(element, prev.next);
    }
    size++;
}

@Override
public E remove(int index) {

//        Node<E> node = first;
//        if (index == 0) {
//            first = first.next;
//        } else {
//            Node<E> prev = node(index -1);
//            node = prev.next;
//            prev.next = node.next;
//        }
        rangeCheck(index);
    Node&lt;E&gt; node = node(index);
    Node&lt;E&gt; prev = node.prev;
    Node&lt;E&gt; next = node.next;

    if (prev == null) { // index == 0
        first = next;
    } else {
        prev.next = next;
    }

    if (next == null) { // index == size - 1
        last = prev;
    } else {
        next.prev = prev;
    }

    size--;
    return node.element;
}

@Override
public int indexOf(E element) {
    if (element == null) {
        Node&lt;E&gt; node = first;
        for (int i = 0; i &lt; size; i++) {
            if (node.element == null) return i;

            node = node.next;
        }
    } else {
        Node&lt;E&gt; node = first;
        for (int i = 0; i &lt; size; i++) {
            if (element.equals(node.element)) return i;

            node = node.next;
        }
    }
    return ELEMENT_NOT_FOUND;
}

/**
 * 获取index位置对应的节点对象
 * @param index
 * @return
 */
private Node&lt;E&gt; node(int index) {
    rangeCheck(index);

    if (index &lt; (size &gt;&gt; 1)) {
        Node&lt;E&gt; node = first;
        for (int i = 0; i &lt; index; i++) {
            node = node.next;
        }
        return node;
    } else {
        Node&lt;E&gt; node = last;
        for (int i = size - 1; i &gt; index; i--) {
            node = node.prev;
        }
        return node;
    }
}

@Override
public String toString() {
    StringBuilder string = new StringBuilder();
    string.append(&quot;size=&quot;).append(size).append(&quot;, [&quot;);
    Node&lt;E&gt; node = first;
    for (int i = 0; i &lt; size; i++) {
        if (i != 0) {
            string.append(&quot;, &quot;);
        }

        string.append(node);

        node = node.next;
    }
    string.append(&quot;]&quot;);
    return string.toString();
}

}

LinkedList和ArrayList的设计

博客内容遵循：署名-非商业性使用-禁止演绎 4.0 国际（CC BY-NC-ND 4.0）
本文永久链接：https://www.wztlink1013.com/blog/nkn2os/
编辑：部署：订阅：中转：

尼采般地抒情

音乐盒

站点信息

JAVA链表设计

LinkedList和ArrayList的设计

接口List设计

抽象类AbstractList设计

ArrayList设计

LinkedList设计

评论区

公告栏

文章分类

最新评论