数据结构和算法杂谈（一）--单向链表

开篇想法

第一次写博客，之前看到很多人说到写博客的好处，总认为自己的能力距离写博客的程度还差得好远。今天突然想通，并没有人规定有多少知识量才可以写博客啊。作为自己学习笔记的记录也是一种很好的方式吧，何必在乎有没有人阅读呢？俗话说好记性不如烂笔头，也许一开始写的很稚嫩，但这毕竟真实的记录了当下的理解，也方便发现错误以及及时纠正。

链表（Linked List）

在一开始使用Java的时候，就会了解到List类的两种常用实例化方式：
1.List<> list = new ArrayList<>();
2.List<> list = new LinkedList<>();
而第二种就是接下来要说的链表结构集合。
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
链表由一系列结点（Node，链表中每一个元素称为一个结点）组成，结点可以在运行时动态生成。

单向链表

单向链表（最简单的链表）中的每个结点包括两个部分：

1. 存储数据元素的数据域（data）
2. 存储下一个节点地址的指针域（next）
   
   因此依据单向链表的结构可以创建一个结点类：

      public class Node{
        	//每个结点的数据
        	private Object data;
        	//每个结点指向下个节点地址的指针域(下一个结点对象)
        	private Node next;
        
    	    public Node(){}
	        public Node(Object data){
	            this.data = data;
	        }
	        public Node(Object data,Node next){
	            this.data=data;
	            this.next=next;
	        }
       }

有了链表的节点类，就可以再建一个链表类（也可以将结点类建在链表类之内）：

	//单独的链表类
      public class SingleLinkedList {
		    //链表包含的结点个数
		    private int size;
		    //头结点
		    private Node head;
			//链表类初始化方法
		    public SingleLinkedList(){
		        size = 0;
		        head = null;
		    }
       }

	//包含结点类的链表类
      public class SingleLinkedList {
      		//链表包含的结点个数
		    private int size;
		    //头结点
		    private Node head;
			//链表类初始化方法
		    public SingleLinkedList(){
		        size = 0;
		        head = null;
		    }
		    private class Node{
	        	//每个结点的数据
	        	private Object data;
	        	//每个结点指向下个节点地址的指针域(下一个结点对象)
	        	private Node next;
	        
	    	    public Node(){}
		        public Node(Object data){
		            this.data = data;
		        }
		        public Node(Object data,Node next){
		            this.data=data;
		            this.next=next;
		        }
	       }
       }

单向链表的操作方法逻辑：

添加
链表添加结点可分为三种方法：

1. 在链表head处添加结点
2. 在链表尾部添加结点
3. 在链表中间添加结点

假设有以下这样一个初始链表以及需要添加的M结点：

首先分析第一种：在链表head处添加结点

先查看链表是为空，将M结点设为head结点，若链表存在结点，将head结点设置为M结点的next结点。

    //在链表头添加元素
    public void addHead(Object m){
        //新建该结点
        Node mNode = new Node(m);
        //判断链表是否有结点
        if(size == 0){
            //若没有，直接将该结点作为链表，该节点的next结点默认为null
            //head为SingleLinkedList的参数
            head = mNode;
        }else{
            //若已有结点，直接将head结点作为M结点的next，将M结点设为head
            mNode.next = head;
            head = mNode;
        }
        size++;
    }

第二种：在链表尾部添加结点

查看列表是否有结点，若没有，设置M结点为尾结点，若有，则遍历出尾结点，将尾结点的next指针指向M结点

    //在链表尾部添加元素
    public void addHeadintail(Object m){
        //新建该结点
        Node mNode = new Node(m);
        //判断链表是否有结点
        if(size == 0){
            //若没有，直接将该结点作为链表，该节点的next结点默认为null
            head = mNode;
        }else{
            //若已有结点，遍历出尾结点
            Node tailNode = head;
            while(tailNode.next!=null){
                tailNode = tailNode.next;
            }
            //将尾结点的next指针指向M结点
            tailNode.next = mNode;
        }
        size++;
    }

第三种：在链表中间添加结点

    //在链表中插入元素
    public boolean addHeadwithNode(Object node,Object m){
        //新建该结点
        Node mNode = new Node(m);
        //判断链表是否有结点
        if(size == 0){
            //若没有结点数据，则直接定义为head结点
            head = mNode;
            size++;
            return true;
        }else{
            //若已有结点，遍历查看是否存在该节点
            Node tailNode = head;
            //遍历出该结点，并设置mNode的next为该结点的next,然后将其next结点指向mNode
            while(tailNode!=null){
                if(tailNode.data.equals(node)){
                    mNode.next=tailNode.next;
                    tailNode.next=mNode;
                    size++;
                    return true;
                }
                tailNode = tailNode.next;
            }
        }
        return false;
    }

删除

此处的删除为若存在相同数据结点，则删除所有重复。
删除的原理是将结点的next越过要删除的结点指向删除节点的next。
思路为：

1. 清除head.data等同于要删除的对象数据，若head的数据等于要删除的数据，则head后移
2. 清理head之后，遍历后面的结点，若结点数据等同于要删除的数据，则该结点的前一结点的next指向该结点的后一结点，使该结点脱离链表。

删除前：

删除后：

//删除指定结点（若存在相同数据结点，则删除所有重复）
    public void delNode(Object m){
        Node tempNode = head;
        //清head
        while(tempNode.data!=null && tempNode.data.equals(m)){
            if(tempNode.data.equals(m)){
                head = tempNode.next;
                size--;
            }
            tempNode = tempNode.next;
        }
        //保证了head.data不是m的情况下，清理下一个data为 m 的结点
        int tempSize = size;
        while(tempSize>1){
            if (tempNode.next!= null && tempNode.next.data.equals(m)){
                tempNode.next=tempNode.next.next;
                size--;
                tempSize--;
            }
            tempNode = tempNode.next;
            tempSize--;
        }
    }

显示
遍历并输出到控制台：

	//显示节点信息
    public void display(){
        if(size>0){
            Node node = head;
            int tempSize = size;
            if(tempSize == 1){
                System.out.println("["+node.data+"]");
                return;
            }
            while(tempSize>0){
                if(node.equals(head)){
                    System.out.print("["+node.data+"->");
                }else if(node.next == null){
                    System.out.print(node.data+"]");
                }else{
                    System.out.print(node.data+"->");
                }
                node = node.next;
                tempSize--;
            }
            System.out.println();
        }else{
            //如果链表没有节点，则打印[]
            System.out.println("[]");
        }
    }

以上即是单向链表的常用操作。

单向链表的常见问题有：

1. 如何将单向链表逆序。例如：将[A->B->C] 逆序为 [C->B->A]
2. 如何只删除单向链表中的出现次数大于1的结点。例如：遍历[A->B->C->B->C->C->D]删除后只留下[A->D]