投稿 资料上传 提问 搜索
您现在的位置是: 首页 > 问答 > 正文

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

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

问题回复
  1. 简讯
    简讯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

     

     

    回复