数据结构--简单链表

一、序言

       数据结构在大学都学过，由于大学认识不够，对这个有点酱油了，很多东西都是知道其概念，当然基本的应用也会，但是偶尔的面试等一些地方的应用，还是不够，这里再复习一些知识，给大家分享，知识来源于数据结构的书和网上的东西。

 

二、抽象数据类型

       ADT（abstract data type）是带有一组操作的的的一些对象的集合。对于集合的ADT，我的理解是：拥有对数据的存放结构的定义（比如Node、List），是一种自定义的数据结构，同时含有对这些元素进行操作的描述（比如：add、remove、insert），这些都是没有具体实现，但是可以通过这些定义和描述我们可以进行分析和研究，同时给实现留下空间，JAVA 集合里面对这块做了多种实现。

 

三、简单链表

       简单链表包含了存储元素和指向下一个元素的“指针”，这里我们仅通过图进行简单描述：

       

 

     可以看出，上面有一个头节点，通过next 连接和后续节点，最后一个节点指向null.我们可以创建自己的单链表：

     

// 我们先定义一个简单的节点形式的结构
public  class Node<T> {
	T element;
	Node<T> next;
}

    

// 通过节点，可以实现简单链表
public class LinkNode<T> extends Node<T>{
	// 头结点
	private Node<T> head = null;
	public LinkNode(){head = new Node<T>();}
	
	// 基本方法
	void add(Node<T> node){}
	// 移除
	void remove(Node<T> node){}
	// 指定位置添加
	void insert(Node<T> node,int index){}
	// 查找
	Node<T> find(T t){return null;}
}

 

四、操作分析：

       1.add () 一个节点：下图可以看出我们默认添加到头节点，讲原来head 结点的执行改变，同时将新节点的next 指向下个节点就行了。当然我们也可以放在末尾，原理类似。

       
        
 
      2.remove() 移除：假设我要移除第二个节点，那么仅仅需要将第一个节点的next 指向第三个就行了。

  

 

    3.find(Node node) 查找：链表的查找会从头开始遍历，和每一个元素进行匹配，循环依次next,显然这个是线性查找，效率没数组那么快，当然在设计过程中，我们可以通过插入时排序，数组存放元素灯方式节省时间，当然会浪费一部分插入的时间，或者存储空间。

     

 
 

     4.insert(Node node,int index) 指定位置插入，这个就不贴图了，可以在next 移动的时候记录下标，在下标为index 的位置插入就行了。

 

五、单向链表反转：这里的反转分为有头结点和没有头节点的情况，但是原理都差不多，这里为了上图理       解，我们用有头节点的情况。

    1.先判断头节点的next 是否存在元素节点，如果存在元素的情况下，还得判断第一个元素的next 是否还有节点，如果没有，表示只有一个节点，直接就返回了，没必要反转。

    2.在有头节点的情况，原理差不多，我们先把头结点隔离开，然后把第一个节点断开，并且指向null,为了能继续找到下面的节点，我们需要一个临时变量，将后面的节点连接起来，现在的图为：

     
    
       
 
      3.然后我们将cur 指向下一个节点C，节点B 的next 指向A(first),同时移动之后将B作为first节点，等待下一次连接，如图：

       
      
 

      

    4.反复执行该操作，直到最后一个节点（C）指向B，这时候cur = null，first = C节点，最后将头节点head 指向 first 节点就行了。

      

Node<T> reverse(Node<T> node){
		Node<T> first;
		Node<T> cur;
		// 判断是否有下一个节点（A）,临时节点保存（B后续节点）
		if((first = node.next) == null || (cur = first.next) == null){
			return node;
		}
		// 头节点断开
		node.next = null;
		// 断开第一个有效节点(A)
		first.next = null;
		while(cur != null){
			Node<T> temp = cur.next;
			// 当前节点的指针，反向指向前一个
			cur.next = first;
			// 这个节点从新作为前节点，等待下一次反向
			first = cur;
			// 从新指定当前节点
			cur = temp;
		}
		node.next = first;
		return node;
	}

 

         4. 对于无头节点的链表，没那么麻烦，仅仅断开第一个节点，从后往前就行了。

 

 

小结：

        1.简单链表，相信大家都懂，各种实现也比我清楚，之所以写这个东西，是因为上次面试有个题，我写了20分钟，想着如何精简代码，如何快速，最后都不敢确定写正确与否，很受打击，也狠狠的鄙视下自己。当然这并不能说明我不会，像很多的排序算法一样，也许我们都知道原理，但是偶尔的一道算法题，不让你上机测试，直接写代码，我相信会有很多人写出来，都不敢保证自己的写的一定正确！确实有一定状态、运气等成分，但是有些基础的东西，以为掌握了，但是在没完全掌握的情况下，还是得进行一些复习吧。

        2.最近看大家聊得最多的什么分布式、高并发、大数据，包括自己也在买书研究，往往忽略的一些基础，也给大家提个醒，抽时间再深入下基础，这些框架实现原理也是基础牢靠了，自己也能实现的，没想象的那么难，最后还是希望大家开心的工作吧~。~