数据结构（1）单链列表-JAVA的实现

数据结构仍然非常重要java 链表，即使它并不出色，但至少您需要了解基础知识，本系列文章旨在回顾您之前学习的数据结构并填补您的知识空白. . 按链接列表，堆栈，队列，排序，数组，树的顺序学习数据结构的过程.

-WZY

首先，单个链接列表的概念

链表是最基本的数据结构，存储如下图所示

上面显示了单个链表的存储原理图. 它简单易懂. head是头节点. 他不存储任何数据. 它仅充当指向链接列表中存储的实际数据的第一节点. 每个节点都有一个下一个引用，指向下一个节点，因此逐个记录下来，直到最后一个节点，下一个指向空.

链接列表有很多种，例如单链接列表，双链接列表等等. 我们将研究单链列表，其他原理实际上是相同的.

第二，使用Java实现单链表

语言只是一种工具. 数据结构真正理解的是这种想法. 这句话确实是真的. 无论写什么，思想都不会改变. 我过去曾经使用C ++，但现在我使用Java逐步实现它.

2.1. 编写一个Node类以用作节点模型. 我们知道有两个属性，1存储数据的数据，2存储下一个节点的引用，

package com.wuhao.demo01;
public class Node {
    //为了方便，这两个变量都使用public，而不用private就不需要编写get、set方法了。
    //存放数据的变量，简单点，直接为int型
    public int data;
    //存放结点的变量,默认为null
    public Node next;
    
    //构造方法，在构造时就能够给data赋值
    public Node(int data){
        this.data = data;
    }
}

查看代码

2.2. 单个链表的简单操作（添加，删除，获取总长度，链表元素的排序，链表遍历）

2.2.1. 添加节点操作，addNode（节点）

想法: 一开始，我认为是否没有节点. 是否需要判断是否插入了第一个节点，但是写入后没有必要，并且第一个节点的操作是相同的，因此通过移动指针以找到最后一个节点来遍历整个链表，只需添加它后来. 没有困难.

    /**
     * 增加操作
     *         直接在链表的最后插入新增的结点即可
     *         将原本最后一个结点的next指向新结点
     */
    public void addNode(Node node){
        //链表中有结点，遍历到最后一个结点
        Node temp = head;    //一个移动的指针(把头结点看做一个指向结点的指针)
        while(temp.next != null){    //遍历单链表，直到遍历到最后一个则跳出循环。
            temp = temp.next;        //往后移一个结点，指向下一个结点。
        }
        temp.next = node;    //temp为最后一个结点或者是头结点，将其next指向新结点
    }

查看代码

2.2.2. 将节点插入到链表的指定位置. insertNodeByIndex（整数索引，节点节点）

注意: 您需要知道插入操作的前提是什么，以便可以编写代码. 写入后，请考虑是否将其插入特殊位置是否相同. 还需要判断插入位置是否可行.

    /**
     * insertNodeByIndex:在链表的指定位置插入结点。
     *         插入操作需要知道1个结点即可，当前位置的前一个结点
     * index:插入链表的位置，从1开始
     * node:插入的结点
     */
    public void insertNodeByIndex(int index,Node node){
        //首先需要判断指定位置是否合法，
        if(index<1||index>length()+1){
            System.out.println("插入位置不合法。");
            return;
        }
        int length = 1;            //记录我们遍历到第几个结点了，也就是记录位置。
        Node temp = head;        //可移动的指针
        while(head.next != null){//遍历单链表
            if(index == length++){        //判断是否到达指定位置。
                //注意，我们的temp代表的是当前位置的前一个结点。
                //前一个结点        当前位置        后一个结点
                //temp            temp.next     temp.next.next
                //插入操作。
                node.next = temp.next;            
                temp.next = node;                
                return;
            }
            temp = temp.next;
        }
    }

查看代码

2.2.3，删除指定位置的节点delNodeByIndex（int索引）

    /**
     * 通过index删除指定位置的结点,跟指定位置增加结点是一样的，先找到准确位置。然后进行删除操作。
     *             删除操作需要知道1个结点即可：和当前位置的前一个结点。
     * @param index：链表中的位置，从1开始
     * 
     */
    public void delNodeByIndex(int index){
        //判断index是否合理
        if(index<1 || index>length()){
            System.out.println("给定的位置不合理");
            return;
        }
        //步骤跟insertNodeByIndex是一样的，只是操作不一样。    
        int length=1;
        Node temp = head;
        while(temp.next != null){
            if(index == length++){
                //删除操作。
                temp.next = temp.next.next;    
                return;
            }
            temp = temp.next;
        }    
    }

查看代码

2.2.4，用于选择排序的单个链接列表selectSortNode（）

前提是要知道什么是排序，否则请查看我的文章以解释排序

分析

    /**
     * 对链表中的结点进行排序，按照从小到大的顺序，使用选择排序。
     *         使用双层遍历。第一层遍历，正常遍历链表，第二层遍历，遍历第一层遍历时所用的结点后面所有结点并与之比较
     *         选择排序比较简单，明白其原理，就能够写的出来。
     */
    public void selectSortNode(){
        //判断链表长度大于2，不然只有一个元素，就不用排序了。
        if(length()<2){
            System.out.println("无需排序");
            return;
        }
        //选择排序
        Node temp = head;            //第一层遍历使用的移动指针，最处指向头结点，第一个结点用temp.next表示
        while(temp.next != null){    //第一层遍历链表，从第一个结点开始遍历
            Node secondTemp = temp.next;        //第二层遍历使用的移动指针，secondTemp指向第一个结点，我们需要用到是第二个结点开始，所以用secondNode.next
            while(secondTemp.next != null){//第二层遍历,从第二个结点开始遍历
                if( temp.next.data > secondTemp.next.data){    //第二层中的所有结点依次与第一次遍历中选定的结点进行比较，
                    int t = secondTemp.next.data;
                    secondTemp.next.data =  temp.next.data;
                    temp.next.data = t;                
                }
                secondTemp = secondTemp.next;
            }
            temp = temp.next;
        }        
    }

查看代码

2.2.5，用于插入排序的单个链接列表insertSortNode（）

前提条件: 要知道什么是插入排序. 很长时间以来java 链表，我都使用插入排序为我编写了这种文本，并且具有相同的强制状态，而且我认为自己的编写效率不是很高. 无论如何，这是mu子和马.

    /**
     * 对链表进行插入排序，按从大到小的顺序，只要这里会写，那么手写用数组插入排序
     *    也是一样的。先要明白原理。什么是插入排序，这样才好写代码。
     *    插入排序：分两组，一组当成有序序列，一组当成无序，将无序组中的元素与有序组中的元素进行比较(如何比较，那么就要知道插入排序的原理是什么这里不过多阐述)
     *        这里我想到的方法是，构建一个空的链表当成有序序列，而原先的旧链表为无序序列，按照原理，一步步进行编码即可。
     *    
     */
    public void insertSortNode(){
        //判断链表长度大于2，不然只有一个元素，就不用排序了。
        if(length()<2){
            System.out.println("无需排序");
            return;
        }
        //创建新链表
        Node newHead = new Node(0);    //新链表的头结点
        Node newTemp = newHead;        //新链表的移动指针
        Node temp = head;        //旧链表的移动指针
        if(newTemp.next == null){        //将第一个结点直接放入新链表中。
            Node node = new Node(temp.next.data);
            newTemp.next = node;
            temp = temp.next;    //旧链表中指针移到下一位(第二个结点处)。
        }
        while(temp.next != null){     //    遍历现有链表
            while(newTemp.next != null){
                //先跟新链表中的第一个结点进行比较,如果符合条件则添加到新链表，注意是在第一个位置上增加结点
                //如果不符合，则跟新链表中第二个结点进行比较，如果都不符合，跳出while，判断是否是到了新链表的最后一个结点，如果是则直接在新链表后面添加即可
                
                if(newTemp.next.data < temp.next.data){
                    Node node = new Node(temp.next.data);
                    node.next = newTemp.next;
                    newTemp.next = node;
                    break;
                }
                newTemp = newTemp.next;
            }
            if(newTemp.next == null){//到达最末尾还没符合，那么说明该值是新链表中最小的数，直接添加即可到链表中即可
                //直接在新链表后面添加
                Node node = new Node(temp.next.data);
                newTemp.next = node;
            }
            //旧链表指针指向下一位结点，继续重复和新链表中的结点进行比较。
            temp = temp.next;
            //新链表中的移动指针需要复位，指向头结点
            newTemp = newHead;            
        }
        //开始使用新链表，旧链表等待垃圾回收机制将其收回。
        head = newHead;
    }

查看代码

2.2.6. 当然，您也可以使用冒泡排序，合并排序等，您可以自己尝试，我不会编写. 如果您不理解这些类型，请查看我写的文章.

2.2.7. 计算单链表的长度

    /**
     * 计算单链表的长度，也就是有多少个结点
     * @return    结点个数
     */
    public int length() {
        int length=0;
        Node temp = head;
        while(temp.next != null){
            length++;
            temp = temp.next;
        }
        return length;
    }

查看代码

2.2.8，遍历单链列表，打印数据

    /**
     * 遍历单链表，打印所有data
     */
    public void print(){
        Node temp = head.next;
        while(temp != null){
            System.out.print(temp.data+",");
            temp = temp.next;
        }
        System.out.println();
    }

查看代码

三，总结

上面的基本单链列表操作. 自己手动编写它会极大地帮助您理解单链列表的数据结构. 当然，最困难的部分是链表的排序. 不难说，只要您了解几种原理，就如同编写伪代码并实现它一样. 这里有一些操作，您可以自己做，我将在下一篇文章中解释这些答案.

3.1. 如何从链表中删除重复数据

3.2. 如何在单链列表中找到倒数第二个元素

3.3. 如何反向链接列表

3.4. 如何从头到尾输出单链列表

3.5. 如何找到单链列表的中间节点

3.6. 如何检测链表是否有环

3.7. 如何在不知道头节点的情况下删除指定节点

3.8. 如何判断两个链表是否相交

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-197435-1.html