Java实现一个双向链表的倒置功能-IT技术之家

提问搜索

您现在的位置是：首页 > 问答 > 正文

Java实现一个双向链表的倒置功能

剪剪清风

IT技术之家

2020/4/13 16:22 71

题目要求：实现一个双向链表的倒置功能（1->2->3 变成 3->2->1)
要求成果物：代码、测试用例（单元测试）
Tips：认真审题，请勿直接使用JDK的LinkedList。

问题回复

简讯IT技术之家

双向链表类代码：

 public class DoubleLinkedList<E> {
    transient Node<E> first; //头节点
    transient Node<E> last; //尾节点
    transient int size = 0; //节点个数
 
    public DoubleLinkedList() {
    }
 
    /**
     * 判断是否为空
     *
     * @return true 为空, false 不为空
     */
    public boolean isEmpty() {
        return 0 == size;
    }
 
    /**
     * 获取表元素个数
     *
     * @return 表链元素个数
     */
    public int size() {
        return size;
    }
 
    /**
     * 反序排列列表中的值
     */
    public void reverse() {
        if (isEmpty()) {
            return;
        }
        // 表的头节点与尾节点互换位置
        Node<E> temp = first;
        first = last;
        last = temp;
 
        // 从表头按序遍历 更每个新节点的前后节点互换
        Node<E> n = first;
        while (n != null) {
            temp = n.next;
            n.next = n.per;
            n.per = temp;
            n = n.next;
        }
    }
 
    /**
     * 根据索引获取元素
     *
     * @param index 元素
     * @return
     */
    public E get(int index) {
        checkIndex(index);
        return getNode(index).item;
    }
 
    /**
     * 将元素追加到列表的末尾
     *
     * @param item 元素
     */
    public void add(E item) {
        Node<E> l = last;
        Node<E> newNode = new Node(l, item, null);
        last = newNode;
        if (l == null) {
            first = newNode;
        } else {
            l.next = newNode;
        }
        size++;
    }
 
    /**
     * 根据索引获取节点
     *
     * @param index 索引
     * @return 节点
     */
    private Node<E> getNode(int index) {
        if (index < (size >> 2)) { //如果索引在列表前面 正序遍历
            Node<E> node = first;
            for (int i = 0; i < index; i++) {
                node = node.next;
            }
            return node;
        } else { //否则倒叙遍历
            Node<E> node = last;
            for (int i = size - 1; i > index; i--) {
                node = node.per;
            }
            return node;
        }
    }
 
    /**
     * 检查索引值
     *
     * @param index 索引
     */
    private void checkIndex(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }
    }
 
    /**
     * 节点元素
     *
     * @param <E>
     */
    private class Node<E> {
        E item;//元素的值
        Node per;// 前一个结点
        Node next;// 后一个结点
 
        public Node(Node per, E item, Node next) {
            this.item = item;
            this.per = per;
            this.next = next;
        }
 
        public String toString() {
            return item + "";
        }
    }
 
    /**
     * 自定义个一个列表迭代器
     *
     * @return
     */
    public Iterator<E> iterator() {
        return new Itr();
    }
 
    private class Itr implements Iterator<E> {
 
        int cursor = 0;
        int lastRet = -1;
 
        public boolean hasNext() {
            return cursor != size();
        }
 
        public E next() {
            try {
                E next = get(cursor);
                lastRet = cursor++;
                return next;
            } catch (IndexOutOfBoundsException e) {
                throw new NoSuchElementException();
            }
        }
 
        public void remove() {
            if (-1 == lastRet) {
                throw new IllegalStateException();
            }
            throw new RuntimeException("remove is denied");
        }
    }
}

下面在创建一个测试用例：

public class DoubleLinkedListTest {
 
    /**
     * 链表打印
     *
     * @param list
     */
    public static void printDoubleLinkedList(DoubleLinkedList<Integer> list) {
        StringBuffer sb = new StringBuffer();
        Iterator<Integer> it = list.iterator();
        while (it.hasNext()) {
            sb.append(it.next());
            if(it.hasNext()) {
                sb.append("->");
            }
        }
        System.out.println(sb.toString());
    }
 
    public static void main(String[] args) {
 
        DoubleLinkedList<Integer> list = new DoubleLinkedList<Integer>();
        list.add(1);
        list.add(2);
        list.add(3);
 
        System.out.println("链表倒置前:");
        printDoubleLinkedList(list);
 
        list.reverse();
 
        System.out.println("链表倒置后:");
        printDoubleLinkedList(list);
    }
}

转载->会敲代码的小蜜蜂：https://blog.csdn.net/bluerebel/article/details/85201906

2020/4/13 16:26回复

友情提示