2010_线性表之链表之双向链表

2.2.2 双向链表

2.2.2.1 API设计

类名 Node
构造器 Node(T t, Node pre, Node next)
成员变量 T item;存储数据
Node next;指向下一个结点
Node pre;指向上一个结点

双向链表API与单向链表一致, 添加如下方法

public T getFirst()获取第一个元素
public T getLast();获取最后一个元素

2.2.2.2 代码实现

package b_linear.b_linkedlist;

import java.util.Iterator;

public class TwoWayLinkList<T> implements Iterable{
    //成员变量
    private Node<T> head;
    private Node<T> last;
    private int n;




    //成员内部类
    private class Node<T> {
        //成员变量: 存储元素
        public T item;
        //下一个结点
        public Node next;
        public Node pre;

        public Node(T item, Node pre, Node next) {
            this.item = item;
            this.pre = pre;
            this.next = next;
        }
    }

    //构造器
    public TwoWayLinkList() {
        //初始化头结点
        this.head = new Node(null, null, null);
        //初始化尾结点
        this.last = null;

        //初始化元素个数
        this.n = 0;
    }

    //成员方法
    //清空
    public void clear() {
        this.head.next = null;
        this.last = null;
        this.n = 0;
    }

    //获取长度,即元素个数
    public int length() {
        return this.n;
    }

    //是否为空
    public boolean isEmpty() {

        return this.n == 0;
    }

    //获取第一个元素
    public T getFirst() {
        if (isEmpty()) {
            return null;
        }
        return (T) this.head.next.item;
    }

    //获取最后一个元素
    public T getLast() {
        if (isEmpty()) {
            return null;
        }
        return this.last.item;
    }

    //获取元素
    public T get(int i) {
        //通过循环, 从头结点开始往后, 依次找到i位置
        Node<T> node = head.next;
        for (int index = 0; index < i; index++) {
            node = node.next;
        }
        return node.item;
    }

    //添加元素
    public void insert(T t) {
        //如果链表为空
        if (isEmpty()) {
            //创建新结点
            Node newNode = new Node(t, head, null);
            //新结点成为尾结点
            last = newNode;
            //头结点指向尾结点
            head.next = last;
        } else {
            //如果不为空
            Node oldLast = last;
            //创建新结点
            Node newNode = new Node(t, oldLast, null);

            //当前尾结点指向尾结点
            oldLast.next = newNode;

            //新结点成为尾结点
            last = newNode;
        }
        //元素个数加1
        this.n++;
    }

    //指定位置添加元素
    public void insert(int i, T t) {
        //找到i位置的前一个结点
        Node pre = head;
        for (int index = 0; index < i; index++) {
            pre = pre.next;
        }
        //找到i位置的结点
        Node curr = pre.next;

        //创建新结点
        Node newNode = new Node(t, pre, curr);

        //让i位置的前结点的下一个结点为新结点
        pre.next = newNode;
        //i位置的前一个结点变为新结点
        curr.pre= newNode;

        //元素个数加 1
        this.n++;
    }

    //删除i位置处的元素
    public T remove(int i) {
        //找到i前一个位置的结点
        Node<T> pre = head;
        for (int index = 0; index <= i - 1; index++) {
            pre = pre.next;
        }
        //找到i位置的结节
        Node<T> curr = pre.next;
        //找到i位置下一个结点
        Node<T> nextNode = curr.next;
        //前一个节点指向下一个结点
        pre.next = nextNode;
        //下一个结点指向前一个结点
        nextNode.pre = pre;

        //元素个数一1
        this.n--;
        return curr.item;
    }

    //查找元素首次出现位置
    public int indexOf(T t) {
        //从头结点开始, 依次找出每一个结点, 取出item与t比较, 如果相迥找到了
        Node<T> node = head;
        for (int i = 0; node.next != null; i++) {
            node = node.next;
            if (node.item.equals(t)) {
                return i;
            }
        }
        return -1;
    }


    @Override
    public Iterator iterator() {
        return new TIterator();
    }
    private class TIterator implements Iterator {
        private Node node;
        public TIterator() {
            this.node = head;
        }
        @Override
        public boolean hasNext() {
          return node.next != null;
        }

        @Override
        public Object next() {
            node = node.next;
            return node.item;
        }
    }
}

2.2.2.3 测试

package b_linear.b_linkedlist;

/**
 * 双向链表测试
 */
public class TwoWayLinkListTest {
    public static void main(String[] args) {
        //创建对象
        TwoWayLinkList<String> s1 = new TwoWayLinkList<>();
        //插入
        s1.insert("姚明");
        s1.insert("科比");
        s1.insert("麦迪");
        s1.insert(1, "詹姆斯");

        for(Object s : s1) {
            System.out.println((String)s);
        }
        System.out.println("-----");

        System.out.println("第一个: " + s1.getFirst() );
        System.out.println("最后一个: " + s1.getLast() );

        //获取
        String getResult = s1.get(1);
        System.out.println(getResult);

        //删除
        String removeResult = s1.remove(0);
        System.out.println(removeResult);


        //清空
        s1.clear();
        System.out.println("清空后的元素个数: " + s1.length());

    }
}

2.2.3 链表复杂度分析

1. get(int i)方法 复杂度为O(n)
2. inser(int i, T t); 复杂度为O(n)
3. remove(int i); 复杂度为O(n)

增删有优势, 初始化时不需要指定长度.

2.2.4 链表反转

1. 实现

    //链表反转
    public void reverse(){
        if(isEmpty()) {
            return;
        }
        reverse(head.next);
    }
    public Node reverse(Node curr) {
        if(curr.next == null) {
            head.next = curr;
            return curr;
        }
        //递归反转curr下一个结点, 返回值为当前结点的上一个结点
        Node pre = reverse(curr.next);
        //返回的结点的下一个结点变为前结点curr
        pre.next = curr;
        //当前结点的下一个结点变为null
        curr.next = null;
        return curr;
    }
   

2. 测试

   package b_linear.b_linkedlist;

   /**

   • 单向链表测试
     */
     public class LinkListTest2 {
     public static void main(String[] args) {
     //创建对象
     LinkList s1 = new LinkList<>();
     //插入
     s1.insert("姚明");
     s1.insert("科比");
     s1.insert("麦迪");
     s1.insert(1, "詹姆斯");

      for(Object s : s1) {
          System.out.println((String)s);
      }
      System.out.println("-----");
     
      //反转
      s1.reverse();
      for(Object s : s1) {
          System.out.println((String)s);
      }
     

     }
     }

测试结果

姚明
詹姆斯
科比
麦迪
-----
麦迪
科比
詹姆斯
姚明

2010_线性表之链表之双向链表

原文：https://www.cnblogs.com/coder-Joe/p/13697783.html