数据结构——链表

链表

链表是链式存储

链表的节点有两部分组成：value和next

java如何构建节点呢？

java的内存分为栈和堆内存

栈中往往存放变量。堆中往往存放对象

每个节点在java中都可以视为一个对象：对象中存在两个全局变量也就是value和next值

那么对象如何创建呢？

类是对象的模板

package com.qcby.datastructure.List;

public class ListNode {
   
    int value;//节点的数据区域
    ListNode next;//记录下一个节点的地址
    //构造器、
    public ListNode(int value) {
   
        this.value = value;
    }
     @Override
    public String toString() {
   
        return "ListNode{" +
                "value=" + value +
                ", next=" + next +
                '}';
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

package com.qcby.datastructure.List;

public class Test {
   
    public static void main(String[] args) {
   
        ListNode node1 = new ListNode(3);
        ListNode node2 = new ListNode(4);
    }
}
1
2
3
4
5
6
7
8
9
10

问题一：next为什么是ListNode类型的数据

Java是强类型语言。定义什么样的类型就是要在内存中开辟什么样的空间。如int类型就只开辟32bit空间（1符号位31数值位）

ListNode node1 = new ListNode(3);

我们直接访问node 的时候，得到的是地址的值。说明node1在堆内存当中存储着ListNode类型对象的地址，而next是存放下一个ListNode类型对象的地址，node1是ListNode类型，那么next也只能是ListNode类型

链表的插入

尾插法

插入的数据是顺序

package com.qcby.datastructure.List;

public class LinkList {
   

    public ListNode head =null;

    /**
     * 尾插法
     * @param value，要插入的值
     */
    public void insert(int value){
   
        ListNode listNode =new ListNode(value);
        if (head==null){
   
            head = listNode;
            return;
        }
        ListNode indexNode = head;
        while (indexNode.next !=null){
   
            indexNode = indexNode.next;
        }
        listNode.next=listNode;
    }
}

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

package com.qcby.datastructure.List;

public class Test {
   
    public static void main(String[] args) {
   
        LinkList linkList =new LinkList
1
2
3
4
5
6