链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针实现的。链表由一系列结点组成，结点可以在运行时动态生成，而且由于没有闲置的内存，因此空间效率比数组高。其插入操作可达到O(1)复杂度，但是查找或者访问特定的结点复杂度是O(n)。
链表的实现可以是单向链表或者双向链表，LinkedList的底层就是双向链表，本文介绍单向链表的简单操作。
1.内部类声明LinkNode节点，其中需要有节点数据的声明以及下一个节点的引用声明。
2.在MyLink类中声明head头节点，初始值为null。
3.add()方法实现，每次添加都需要new一个节点，将数据封装进节点,下个节点的引用设为null。然后判断头节点是否为null，如果是说明链表是空链表，直接将当前节点设置为头节点。头节点非空的情况下，需要遍历整个链表，找到尾节点，添加节点。找到尾节点，将其对下一个节点的引用设置为新节点就可以了。其中注意节点的遍历，设置一个中间量temp引用头节点head，对其进行操作，temp=temp.next，这样便不会影响原来的head节点。
4.delete()方法实现，根据数据删除节点需要涉及到前向节点的操作，头节点没有前向节点需要单独处理。如果删除的是头节点的数据，直接将下一个节点设置为头节点。不是头节点的情况下，需要遍历找到此节点的位置。如果找到的数据和当前节点的下一个节点数据匹配，直接将当前节点对下一个节点的引用指向再下一个节点。其中设计巧妙的地方在于，需要当前节点和第二个后项节点产生关系，所以判断数据data==temp.next.data为下一个节点数据的判断，然后temp.next==temp.next.next就可以使当前节点和第二个后项节点产生关系。巧妙处还在于直接避开了头节点和尾节点，尤其是尾节点，虽然不在while循环中，但是操作了尾节点。
5.根据索引，查找索引处的数据。链表不支持随机访问，索引访问和数组不一样，是依次查找，直到索引处将数据返回。
6.toString()方法实现，使用StringBuilder拼接字符串，遍历循环就可以了。
网友评论