Java实现单链表基本操作

绝地灬酷狼 2022-02-04 13:51 202阅读 0赞

### 一、 实现单链表数据结构 ###

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

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

#### 2.1 头插法建立链表： ####

public Node insertHead(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;//去掉伪结点
    }

#### 2.2 尾插法建立单链表 ####

public Node insertTail(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.3 求单链表长度 ####

//单链表的长度即单链表中结点的个数，最后一个节点的指针域为空；

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;
            }
        }

#### 2.4 插入一个节点 ####

//生成一个新结点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;
        }

#### 2.5 删除一个结点 ####

//跟插入一个结点类似，删除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;
            }
        }

#### 2.6 按值查找结点 ####

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

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;
            }
        }

#### 2.7 遍历链表 ####

//最后一个结点的指针域为空，扫描链表并显示数据域直到指针域为空。

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;
                }
            }
        }