本文共 4389 字，大约阅读时间需要 14 分钟。

链表

链表是一种物理存储结构上非连续存储结构，逻辑顺序是通过链表中的引用链接次序来实现的。

链表实际就是一个一个节点链接形成的。 所有的链表分为： 1.单向、双向 //单向存有next的地址，而双向不仅存有next的地址，还有prev的地址 2.带头、不带头//带头就是有头节点，不带头就是无头节点（带头链表中，第一个节点中只存储了下一个节点的地址，并无数据，而这个节点就叫头节点） 3.循环、不循环//循环就是最后一个节点的下一个地址为第一个节点的地址，而不循环的最后一个节点的地址为null（一般把第一个节点也叫头节点，最后一个节点叫尾节点） 组合起来就有8种链表结构。

无头单向不循环链表的实现

实现无头单向不循环链表的打印，查找节点，输出查找节点下标，删除查找出的第一个元素，删除所有查找出的元素，获取节点个数等功能

主函数

public class Demo11 {       public static void main(String[] args) {           MyList list = new MyList();        list.create();//穷举建4个节点，若链表为空直接添加，若不为空则尾插        list.show();//输出链表中的数据        list.addHead(6);//头插法插入一个节点        list.show();        list.addLast(8);//尾插法插入一个节点        list.show();        list.create();        list.show();        list.addAny(999,9);//在9位置插入一个999的节点，第一个节点位置为0，此时999的位置为9        list.show();        System.out.println(list.size);        System.out.println("---------------------------");        System.out.println(list.Key(999));//查找999这个数据是否存在在链表的节点里        System.out.println(list.keyNum(999));//输出999的下标        System.out.println("---------------------------");        list.delKey(999);//删除第一次找到的999        list.show();        System.out.println(list.size);        System.out.println("---------------------------");        list.del(1);//删除所有找到的1        list.show();        System.out.println(list.size);    }}

链表、功能、节点等

public class MyList {       public Node head = null;    public int size = 0;//size存储长度    public void create() {   //穷举        if (size==0){   //如果链表为空 则直接添加，否则尾插法添加        Node node1 = new Node(1);        Node node2 = new Node(2);        Node node3 = new Node(3);        Node node4 = new Node(4);        node1.next = node2;        node2.next = node3;        node3.next = node4;        this.head = node1;        size = 4;        }else{               Node cur = this.head;            for (;cur.next!=null;cur = cur.next);            Node node1 = new Node(1);            Node node2 = new Node(2);            Node node3 = new Node(3);            Node node4 = new Node(4);            node1.next = node2;            node2.next = node3;            node3.next = node4;            cur.next=node1;            size = size+4;        }    }    public void addHead(int val){   //头插法        Node node = new Node(val);        node.next = this.head;        this.head = node;        size ++;    }    public void addLast(int val) {   //尾插法        Node cur = this.head;        if (cur == null){               Node node = new Node(val);            this.head = node;        }        for (;cur != null;){               if (cur.next == null) {                   Node node = new Node(val);                cur.next = node;                size ++;                return;            }            cur = cur.next;        }    }    public void addAny(int val,int pos){   //任意位置插入，头结点为0        Node cur = this.head;        int i;        if (pos<0||pos>size){               System.out.println("pos位置不合法");            return ;        }else if (pos == 0){               Node add = new Node(val);            add.next = cur;            this.head = add;            size++;            return;        }        for (i = 1; i 

实现逆序

方法1：头插

public void inverse(){   //逆序        if (this.head == null){               return;        }        Node cur = this.head.next ;        this.head.next=null;        for (;cur!=null;cur = cur.next){               addHead(cur.val);//调用头插法，此处必须有头插法，或者把头插法复制过来        }    }

方法2：3个变量进行遍历

public void inverse(){   //逆序	Node perv = this.head;//1	Node cur = this.head.next;//2	Node next = cur.next;//3	this.head.next = null;	for(;next.next!=null;) {   	    cur.next = perv;	    perv = cur;	    cur = next;	    next = next.next;	}	cur.next = perv;	next.next = cur;	this.head = next;}

找出中间节点

快慢两个变量进行变量

public Node midNode (){   //找出中间节点        if (this.head == null){               System.out.println("链表为空");            return null;        }        Node fast = this.head;        Node slow = this.head;        for (;fast.next != null && fast.next.next!=null;){               slow=slow.next;            fast=fast.next.next;        }        if (fast.next==null){               return slow;        }else{               return slow.next;        }    }

内存泄漏的查询（待修改）

1.先进入debug，Node创建完毕后定断点2.wins+r 输入cmd3.输入jps 回车 查看当前JAVA进程号4.输入jmap -histo:live 进程号 > d: aaa.txt  //aaa.txt为临时文件5.然后回到debug，让程序运行完成6.打开那个临时文件，查找类名为（class name）Node的实例有几个7.回到idea，让程序清除运行并运行完成，再重复34步，回到临时文件查找实例。