关于单链表的数据结构的学习

因为之前阅读事件分发的源代码的时候，我们可以在dispatchTouchEvent里面，有一个很关键的字段firstTouchTarget，包括在他的down事件发生的时候调用的addTouchTarget方法以及在move，up事件发生的时候走的流程

                TouchTarget predecessor = null;
                TouchTarget target = mFirstTouchTarget;
                while (target != null) {
                    final TouchTarget next = target.next;
                    if (alreadyDispatchedToNewTouchTarget && target == newTouchTarget) {
                        handled = true;
                    } else {
                        final boolean cancelChild = resetCancelNextUpFlag(target.child)
                                || intercepted;
                        if (dispatchTransformedTouchEvent(ev, cancelChild,
                                target.child, target.pointerIdBits)) {
                            handled = true;
                        }
                        if (cancelChild) {
                            if (predecessor == null) {
                                mFirstTouchTarget = next;
                            } else {
                                predecessor.next = next;
                            }
                            target.recycle();
                            target = next;
                            continue;
                        }
                    }
                    predecessor = target;
                    target = next;
                }

等等，这个时候我们为了看懂他，就必须得了解链表结构的数据，我们可以看到TouchTarget这个对象的源代码

 private static final class TouchTarget {
        private static final int MAX_RECYCLED = 32;
        private static final Object sRecycleLock = new Object[0];
        private static TouchTarget sRecycleBin;
        private static int sRecycledCount;

        public static final int ALL_POINTER_IDS = -1; // all ones

        // The touched child view.
        public View child;

        // The combined bit mask of pointer ids for all pointers captured by the target.
        public int pointerIdBits;

        // The next target in the target list.
        public TouchTarget next;

这是touchTarget的属性，我们这里可以看到他有2个属性

private static TouchTarget sRecycleBin;public TouchTarget next;

其实这里的touchTarget是个单链表结构（为什么不是双链表），因为这个类里面就2个方法一个obtain一个recycle，我们可以看看这个链表去数据的时候，我们可以看到obtain方法的源代码。

public static TouchTarget obtain(@NonNull View child, int pointerIdBits) {
            if (child == null) {
                throw new IllegalArgumentException("child must be non-null");
            }

            final TouchTarget target;
            synchronized (sRecycleLock) {
                if (sRecycleBin == null) {
                    target = new TouchTarget();
                } else {
                    target = sRecycleBin;
                    sRecycleBin = target.next;
                     sRecycledCount--;
                    target.next = null;
                }
            }
            target.child = child;
            target.pointerIdBits = pointerIdBits;
            return target;
        }

这里的child什么字段是数据域的东西，先不去管他，我们看看同步块里的方法，如果sRecycleBin为null就new一个TouchTarget 对象，如果这个不为null,那么就将这个节点赋值给申明的对象，并且节点的后继节点赋值给sRecycleBin，然后这个链表的长度减一，这就相当于是从链表的sRecycleBin地方开始取一个节点，然后sRecycleBin节点的后继节点移动一位，然后链表长度减1，然后将取出的这个节点的指针域赋值为null，就表示取出了一个节点，这里我们可以将sRecycleBin当成是一个游标一样东西，他标识着你从这个链表当中取节点，取的是哪个节点。如果target.next不赋值为null，那么相当于你取的是整个链表了，因为这个节点的指针域指向的是sRecycleBin游标所对应的节点了。至此到这里，所以我们有必要了解下链表结构。如下图 无标题.png

这是一个链表的数据结构，其中每个节点node，就相当于上面的touchTarget对象，而这里的data就相当于是touchTarget里的非touchTarget类型的字段，而next就相当于是public TouchTarget next;属性字段。那么我们自己来玩玩链表，这里我们只玩非循环的单链表。那么我们一般玩一个数据，基本的操作增删改查，排序。所以我们就按照这个功能来玩一玩这个链表的数据结构的增删改查，排序。

public class MyList<T> {


    private Node mFirst;//链表头
    private int count = 0;//链表的长度

    public class Node {
        private T data;
        private Node next;

        public Node(T data, Node node) {
            this.data = data;
            next = node;
        }
    }


    public Node getmFirst() {
        return mFirst;
    }

    private Node searchNode(int index)
    {
        Node target=mFirst;
        for (int i=0;i<index;i++)
        {
            target=target.next;
        }
        return target;
    }

    /**
     * 查询一个节点（查）
     * @param index
     * @return
     */
    public T get(int index)
    {
        return searchNode(index).data;
    }

    /**
     * 添加节点(增)
     * @param data
     */
    public void put(T data)
    {
        if (data==null)
            return;
        if (count==0)//表示为空链表
        {
            mFirst=new Node(data,null);
            count++;
        }else
        {
            //首先要查询链表的最后一个节点
            Node lastNode=searchLastNode();
            lastNode.next=new Node(data,null);
            count++;
        }
    }

    /**
     * 删除一个节点
     * @param index
     * @return
     */
    public boolean delete(int index)
    {
        if (index<0)
            return false;
        Node target=searchNode(index);
        if (index==0)
        {
            mFirst=target.next;//链表首节点后移
            target.next=null;  //要删除的节点的指针域赋值为null
            count--;
            return true;
        }else {
            Node preNode = searchNode(index - 1);
            if (preNode != null) {
                preNode.next = target.next;
                target.next = null;
                count--;
                return true;
            } else {
                return false;
            }
        }
    }


    /**
     * 更新节点
     * @param index
     * @param data
     * @return
     */
    public boolean update(int index,T data)
    {
        Node target=searchNode(index);
        if (target!=null) {
            target.data = data;
            return true;
        }
        return false;
    }

    /**
     * 查询链表的最后一个元素
     * @return
     */
    private Node searchLastNode() {

        Node target=mFirst;
        for (;target.next!=null;target=target.next)
        {
            continue;
        }
        return target;
    }

    public int getCount()
    {
        return count;
    }

}

这就是个单链表的增删改查操作，如果要排序，按照链表的长度的不同会有不同的算法，这个就属于后面的算法的内容了，算法在后面我们在学习。这篇文章是先把单链表的数据结构弄清楚。下篇我会学习双向链表。