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

链表介绍

链表是有序的列表,它在内存中的储存如下:

小结:

(1)链表是以节点的方式来储存. (2)每个节点包含data域,next域:指向下一个节点. (3)链表的各个节点不一定是连续存储. (4)链表分为带头节点的链表和不带头节点的链表.

基础(单)链表的实现

(一)实现添加功能: (1)先创建一个头节点head,作用就是表示单链表的头. (2)后面我们没添加一个节点,就直接加入到链表的最后. 链表遍历: 通过一个辅助变量遍历.

package com.dataStructure.com.dataStructure.linklist;public class SingleLinkListDemo {    public static void main(String[] args) {        HeroNode node1 = new HeroNode(1, "a", "aa");        HeroNode node2 = new HeroNode(2, "b", "bb");        HeroNode node3 = new HeroNode(3, "c", "cc");        SingleLinkedList linkedList = new SingleLinkedList();        linkedList.addNode(node1);        linkedList.addNode(node2);        linkedList.addNode(node3);        linkedList.showlist();    }}//定义linklistclass SingleLinkedList{    //先初始化一个头节点  头节点不要动  不放具体的数据    private HeroNode head = new HeroNode(0,"","");    //添加节点到单向链表    public void addNode(HeroNode node){        HeroNode temp = head;  //因为头节点不能动,所以我们需要一个辅助遍历        while (true){          if(temp.next == null){ //找到最后一个节点              break;          }          temp = temp.next;  //如果没有找到最后节点,将temp后移        }        temp.next = node; //退出循环时  就指向了链表的最后    }    //显示遍历链表    public void showlist(){        if(head.next == null){            System.out.println("linklist is null");            return;        }        //因为头节点不能动,所以我们需要一个辅助遍历        HeroNode temp = head.next;        while (true){            if(temp == null){                break;            }            System.out.println(temp);            temp = temp.next; //temp一定后移  否则就是死循环        }    }}class HeroNode{  //字段可以自己选择    public int no;   //编号    public String name; //名字    public String nickName;  //昵称    public HeroNode next;    public HeroNode(int no,String name,String nickName){        this.no = no;        this.name = name;        this.nickName = nickName;    }    @Override    public String toString() {        return "HeroNode{" +                "no=" + no +                ", name='" + name + '\'' +                ", nickName='" + nickName + '\'' +                '}';    }}

以上代码实现了链表的添加功能,但是存在一个问题,遍历链表,结果显示的顺序和添加的顺序保持一致,但我们想要的结果是链表遍历的结果和编号的结果保持一致,修改如下:

(1)首先找到新添加节点的位置,是通过辅助变量(指针),通过遍历来搞定. (2)新的节点.next = temp.next (3)将temp.next = 新的节点

package com.dataStructure.com.dataStructure.linklist;public class SingleLinkListDemo {    public static void main(String[] args) {        HeroNode node1 = new HeroNode(1, "a", "aa");        HeroNode node2 = new HeroNode(2, "b", "bb");        HeroNode node3 = new HeroNode(3, "c", "cc");        SingleLinkedList linkedList = new SingleLinkedList();        linkedList.addByOrder(node1);        linkedList.addByOrder(node3);        linkedList.addByOrder(node2);        linkedList.showlist();    }}//定义linklistclass SingleLinkedList{    //先初始化一个头节点  头节点不要动  不放具体的数据    private HeroNode head = new HeroNode(0,"","");    //添加节点到单向链表    public void addNode(HeroNode node){        HeroNode temp = head;  //因为头节点不能动,所以我们需要一个辅助遍历        while (true){          if(temp.next == null){ //找到最后一个节点              break;          }          temp = temp.next;  //如果没有找到最后节点,将temp后移        }        temp.next = node; //退出循环时  就指向了链表的最后    }    //显示遍历链表    public void showlist(){        if(head.next == null){            System.out.println("linklist is null");            return;        }        //因为头节点不能动,所以我们需要一个辅助遍历        HeroNode temp = head.next;        while (true){            if(temp == null){                break;            }            System.out.println(temp);            temp = temp.next; //temp一定后移  否则就是死循环        }    }    //根据排名将数据插入到指定位置    public void addByOrder(HeroNode node){        HeroNode temp = head;        boolean flag = false;  //标志当前添加的编号是否存在        while (true){            if(temp.next == null){                break;            }            if(temp.next.no > node.no){                break;            }else if(temp.next.no == node.no){                flag = true;                break;            }            temp = temp.next;        }        if(flag){            System.out.println("当前编号已经存在,不能插入此位置");        }else{            node.next = temp.next;            temp.next = node;        }    }}class HeroNode{    public int no;    public String name;    public String nickName;    public HeroNode next;    public HeroNode(int no,String name,String nickName){        this.no = no;        this.name = name;        this.nickName = nickName;    }    @Override    public String toString() {        return "HeroNode{" +                "no=" + no +                ", name='" + name + '\'' +                ", nickName='" + nickName + '\'' +                '}';    }}

这样改变过后,无论我们怎么添加,遍历的结果都是按照编号的顺序显示的.

(二)链表的修改:

根据链表的编号进行修改,所以链表的编号不能改变.(为了减少代码量,我只列出修改的方法,主函数和其他代码同上)

//修改节点的信息,根据no编号来修改,所以no不可以改变    public void update(HeroNode newNode){        if(head.next == null){            System.out.println("linked list is null");            return;        }        HeroNode temp = head.next;        boolean flag = false;        while (true){            if(temp == null){  //表示已经遍历完该链表                break;            }            if(temp.no == newNode.no){                flag = true;                break;            }            temp = temp.next;        }        if (flag){            temp.name = newNode.name;            temp.nickName = newNode.nickName;        }else{            System.out.println("want to update is not exist");        }    }

(三)删除一个节点,思路如下

(1)我们先找到要删除的这个节点的前一个节点temp (2)temp.next = temp.next.next (3)被删除的节点,将不会有其他的引用指向,会被垃圾回收机制回收.

public void delete(int no){        HeroNode temp = head;        boolean flag = false;        while (true){            if(temp.next == null){                break;            }            if(temp.next.no == no){                flag = true; //找到删除节点的前一个节点                break;            }            temp = temp.next;        }        if(flag){            temp.next = temp.next.next;        }else{            System.out.println("want to delete node is not exist");        }    }

实战练习

(1)求单链表中节点的个数(如果是带有头结点的链表,不统计,因为头结点没有数据)

public static int getLength(HeroNode head){        if(head.next == null){            return 0;        }        int length = 0;        HeroNode cur = head.next;  //没有统计头节点        while (cur != null){            length ++;            cur = cur.next;        }        return length;    }

(2)查找单链表中的倒数第K个节点

解决思路: 1.编写一个方法,接受head节点,同时接受K下标(index) 2.index表示的是倒数第index节点 3.先把链表从头到尾遍历,得到链表的总长度. 4.得到size后,我们从链表的第一个开始遍历,遍历(size-index),就可以得到 5.如果得到了,返回该节点,否则返回null

public static HeroNode findLastIndexNode(HeroNode head,int index){       if(head.next == null){           return null;       }       int size = getLength(head);       if(index <= 0 ||index >size){           return null;       }       HeroNode cur = head.next;       for (int i = 0; i 

(3)单链表的反转

解决思路: 1.先定义一个节点reverseHead = new HeroNode(); 2.从头到尾遍历原来的链表,每遍历一个节点,就将其取出,并放在新链表的reverseHead的最前端. 3.原来链表的head.next = reverseHead.next

public static void reverseList(HeroNode head){        if(head.next == null || head.next.next ==null){ //如果链表为空或者只有一个节点            return ;        }        HeroNode cur = head.next;  //定义一个辅助的指针,帮助我们比那里原来的链表        HeroNode next = null;  //指向当前节点cur的下一个节点        HeroNode reverseHead = new HeroNode(0,"","");        //遍历原来的链表,每遍历一个节点,就将其取出,并放在新链表reverseHead的最前端        while(cur != null){            next = cur.next; //先暂时保存当前节点的下一个节点,因为后面需要使用            cur.next = reverseHead.next;  //将cur的下一个节点指向新的链表的最前端            reverseHead.next = cur; //将cur 连接到新的链表上            cur = next; //让cur后移        }        //将head.next指向reverseHead.next,实现单链表的反转        head.next = reverseHead.next;    }

(4)从尾到头打印单链表,两种方法

1.先将单链表进行反转操作,然后遍历即可(原始的链表结构会发生改变,不建议) 2.可以利用栈这个数据结构,将各个节点压入到栈中,然后利用栈先进后出的特点,就实现了逆序打印的效果

public static void revversePrint(HeroNode head){        if(head.next == null){            return;        }        Stack
   
     stack = new Stack<>();        HeroNode cur = head.next;        while (cur != null){            stack.push(cur);            cur = cur.next;        }        while (stack.size() > 0){            System.out.println(stack.pop());        }    }
   

转载地址：http://fjmzi.baihongyu.com/