链表定义和常用操作

在刷关于链表的题时，因为想在本地的idea里测，需要重新构造一些链表的方法，先对链表进行定义，是由data和next组成。如果是双链表就加一个pre节点。如下：

public class ListNode implements MyList{
    Object data;    //数据
    ListNode next;  //下一个节点
    ListNode pre;   //上一个节点

    public ListNode(Object data) {   //指定一个参数构造
        this.data = data;
    }

在Util类中加一些链表的基本操作：先定义一个接口myList，接口中方法为常见的基本操作，可以方便其他的类实现（java多态）：

public interface MyList extends Iterator {
    //增加一个元素
    void add(Object element);
    //删除指定元素
    void delete(Object element);
    //根据索引删除元素
    void delete(int index);
    //更新元素
    void update(int index, Object newElement);
    //判断元素是否存在
    boolean contains(Object target);
    //查询元素
    Object select(int index);
}

在ListNode中，可以先添加一个add方法和重写toString方法，因为这两个方法太常用：

public class ListNode{
    public Object data;    //数据
    public ListNode next;  //下一个节点
    public ListNode pre;   //上一个节点

    public ListNode(Object data) {   //指定一个参数构造
        this.data = data;
    }

    public void add(Object element) {
        ListNode node = new ListNode(element);
        ListNode cur = this;   //指向当前元素
        while (cur.next!= null){  //有后继节点
            cur = cur.next;
        }
        cur.next = node;
    }


    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("[");
        ListNode p = this;  //取出头
        while (p!= null){   //看是否有data和节点
            sb.append(p.data);//添加第一个
            if (p.next != null){  //下一个节点也有元素
                sb.append("->");
            }
            p = p.next;  //后移
        }
        sb.append("]");
        return sb.toString();
    }

}

测试

public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.add(2);
        head.add(3);
        head.add(2);
        head.add(1);
        System.out.println(head);
        )

[1->2->3->2->1]
Process finished with exit code 0

对myList中方法的实现，相当于写一个LinkedList类。如下：

package 链表;

public class SingleLinkedList implements MyList{
    private ListNode head;
    private ListNode last;
    private int size;   //链表的长度，每次更新都要对其操作
    @Override
    public void add(Object element) {
        if (head == null){  //如果头节点为空
            head = new ListNode(element); //第一次插入的是头
            last = head;   //  下一个节点也赋值，不需要new
        }else {
            last.next = new ListNode(element);  //头不为空，下一个节点插入元素
            last = last.next;   //下一个节点改变
        }
        size++;
    }

    @Override
    public void delete(Object element) {  //删除指定元素
        ListNode p = head;
        ListNode pre = null;
        while (p != null){
            if (p.data.equals(element)){
                if (p == head){
                    head = head.next;
                }else {
                    pre.next = p.next;
                }
                size--;
                break;
            }
            pre = p;
            p = p.next;
        }
    }

    @Override
    public void delete(int index) {  //删除元素
        if (index < 0 || index >= size) return;
        int i = 0;//指针指向的节点索引
        ListNode p = head;  //取头节点
        ListNode pre = null;  //定义一个空节点
        while (p != null){   //扫描到尾节点
            if (i == index){  //看下标是否对应
                if (p == head){
                    head = head.next;  //头节点置为空
                }else {
                    pre.next = p.next;  //非头节点，下一个节点提前
                }
                size--;
                break;  //注意这里，删除以后结束循环
            }
            //下标不对应
            pre = p;   //取这个节点
            p = p.next;  //向下移动
            i++;   //向下移动
        }
    }

    @Override
    public void update(int index, Object newElement) {
        if (index < 0 || index >= size) return;  
        int i = 0;//指针指向的节点索引
        ListNode p = head;  //取头节点
        while (p != null){   //扫描到尾节点
            if (i == index){  //看下标是否对应
                p.data = newElement;
                break;
            }
            //下标不对应
            p = p.next;  //向下移动
            i++;   //向下移动
        }
    }

    @Override
    public boolean contains(Object target) {
        ListNode p = head;
        while (p != null){
            if (p.data.equals(target)){
                return true;
            }
            p = p.next;
        }
        return false;
    }

    @Override
    public Object select(int index) {
        if (index < 0 || index >= size) return null;
        int i = 0;//指针指向的节点索引
        ListNode p = head;  //取头节点
        while (p != null){   //扫描到尾节点
            if (i == index){  //看下标是否对应
                return p.data;
            }
            //下标不对应
            p = p.next;  //向下移动
            i++;   //向下移动
        }
        return null;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("[");
        ListNode p = head;  //取出头
        while (p!= null){   //看是否有data和节点
            sb.append(p.data);//添加第一个
            if (p.next != null){  //下一个节点也有元素
                sb.append(",");
            }
            p = p.next;  //后移
        }
        sb.append("]");
        return sb.toString();
    }

    @Override
    public boolean hasNext() {
        return false;
    }

    @Override
    public Object next() {
        return null;
    }
}