Java数据结构之单链表

概论：以单链表为例，每个存储数据元素的结点包括两个域，即数据域和指针域，正常情况下为操作方便，建立链表的时候会建立一个数据域为空的伪结点作为头结点。这里方便起见不使用泛型，数据类型选用Int。

一、 实现单链表数据结构

public class Node{
    Int data;
    Node next;
    public Node(){
        this.next = null;
    }
}

二、 实现单链表上的基本操作

1. 建立链表
   1.1 头插法建立链表：

   public Node insert_head(int[] arr,Node h){      
   for(int i = 0; i < arr.length; i++){
       Node p = new Node();
       p.data = arr[i];
       p.next = h.next;//改变指针
       h.next = p;//使h的直接后继为p
   }
   return h.next;//去掉伪结点
   }

   1.2 尾插法建立单链表

    public Node insert_tail(int arr[],Node h){
        Node t,p;
        t = h;
        for(int i = 0; i< arr.length; i++){
            p = new Node();
            p.data = arr[i];
            t.next = p;
            t = p;//使t始终指向最后一个元素
        }
        return h.next;
    }

2 求单链表长度
思路：单链表的长度即单链表中结点的个数，最后一个节点的指针域为空；

    public static int size(Node h) {
        if (h == null) {
            return 0;
        } else {
            int count = 1;
            Node p = h.next;
            while (p != null) {
                count++;
                p = p.next;
            }
            return count;
        }
    }

3.插入一个节点
思路：生成一个新结点X插入A、B结点之间，则原本A->B 变为A->X->B，也就是改变A和X指针域的值即可。

    public static Node insert(int data, Node p) {
        Node x = new Node();
        x.data = data;
        if (p == null) {
            p = x;
        } else {
            x.data = data;
            x.next = p.next;
            p.next = x;
        }
        return p;
    }

4.删除一个结点
思路：跟插入一个结点类似，删除A->X->B中的X结点，也就是使得A->B并返回X即可。

    public Node remove(Node h) {
        Node p;
        if (h != null && h.next != null) {
            p = h.next;
            h.next = p.next;//指向p的直接后继结点
            return h;
        } else {
            return null;
        }
    }

5.按值查找结点
思路：从头部开始扫描链表，直到当前结点数据域的值为要查找的值时，返回该结点的指针。

    public static Node search(int data, Node h) {
        if (h == null) {
            return null;
        } else if (h.next == null) {
            return h;
        } else {
            Node p = h.next;
            while (p.data != data) {
                p = p.next;
            }
            return p;
        }
    }

6.遍历链表
思路：最后一个结点的指针域为空，扫描链表并显示数据域直到指针域为空。

    public void display(Node h) {
        if (h == null) {
            System.out.println("h is null");
        } else if (h.next == null) {
            System.out.print(h.data);
        } else {
            while (h != null) {
                System.out.print(h.next.data + " ");//不遍历头结点
                h = h.next;
            }
        }
    }

链表是一种非常灵活的数据结构，不仅可以存储线性表，也可以存储复杂的非线性的数据结构，还有双向链表和循环链表，操作方式略有不同，后面继续整理。