java实现链表_java链表实现

一、链表定义

链表通过指针将一组零散的内存块串联在一起进行使用。
数据格式：

根据上面的图展示，每个内存块可以称为链条的一个“结点”，结点包含了数据和下一个结点的地址；同时有2个结点特殊：第一个结点和最后一个结点，第一个结点称为“头节点”，存储链表基地址，最后一个结点称为“尾节点”，尾节点的下一个结点为空地址 NULL。

二、链表实现定义

public class LinkList<T> {
   
    //结点定义
    private class Node{
   
        //数据
        T item;
        //指向下一个结点
        Node next;
        //构造器
        public Node(T item,Node next){
   
            this.item = item;
            this.next = next;
        }
        public Node(T item){
   
            this.item = item;
        }
    }
    //头结点
    private Node head;
    //尾结点
    private Node tail;
    //结点个数
    private int size;

    //链表定义
    public LinkList(){
   
        this.head = new Node(null,null);
        size = 0;
    }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

三、查找特定位置的链表结点

//查找特定位置的链表结点
    public Node get(int index) {
   
        if (index <0 || index >=this.size){
   
            return null;
        }else{
   
            Node temp = this.head;
            for(int i =1;i<=index;i++){
   
                temp = temp.next;
            }
            return temp;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

四、插入链表结点

注意：
将结点 x 的 next 指针指向结点 b，再把结点 a 的 next 指针指向结点 x，这样才不会丢失指针，导致内存泄漏。

//在链表的第i个位置插入一个值为t数据
    public void insert(int index ,T data) throws Exception{
   
        if(index <0 ||index > this.size){
   
            throw new Exception("插入超出范围");
        }else{
   
            Node newNode = new Node(data);
            //在头结点插入元素
            if (index ==0){
   
                if(this.size >0){
   
                    Node temp = head;
                    newNode.next = temp;
                }
                head = newNode;
            }
            //在尾结点插入元素
            else if(index == this.size){
   
                Node temp = tail;
                temp.next = newNode;
                this.tail  = newNode;

            }else{
   
                //在中间插入元素
                Node preNode = get(index-1);
         
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30