侧边栏壁纸
  • 累计撰写 98 篇文章
  • 累计创建 20 个标签
  • 累计收到 3 条评论

数据结构--链表(java实现)

林贤钦
2020-04-25 / 0 评论 / 9 点赞 / 619 阅读 / 0 字
温馨提示:
本文最后更新于 2020-05-09,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

链表

学习java链表也有好几天了,下面就简单整理一下,对链表还是不够深入了解,后面继续学习继续补充修整

1、什么是链表?

链表是有序的列表,但是它在内存的存储形式如下

链表的存储结构

  • 链表是以节点的方式来存储,是链式存储。看似有序,其实是无序的,只不过链表通过链表中的指针,即节点链接次序实现的。
  • 每个节点都包含data域,next域,next指向下个节点,也就是通过next来实现链表的串联。
  • 链表的各个节点不一定是连续存储的。其实在java中,next也是一个对象,next和下个节点是同一个地址,所以就实现了指向下个节点,简单来说,在java中next就是下个节点。
  • 链表分带头节点和不带头节点,根据实际需求来决定。
  • 链表有好几种,单链表,双链表,环形链表

1、单链表

就是只有一个节点,并且只能指向下一个如

单链表

单链表的应用实例

使用带head头的单链表实现 排序管理完成对单链表的增删查改的操作。

1、先准备一个节点类,和一个单链表

public class SingleLinkedList {
    //初始化头节点,头节点不放任何数据
    private Node head =new Node(0,"") ;
}
class Node<T>{

    public Integer no; //表示节点的序号
    public String name; //节点的名字
    public Node next; //指向下一个节点
    public Node(Integer no,String name){
        this.no=no;
        this.name=name;
    }

    @Override
    public String toString() {
        return "Node{" +
                "no=" + no +
                ", name='" + name + '\'' +
                '}';
    }
}

2、第一种方法添加节点,直接添加到链表的尾部

思路:

1. 先创建一个head头节点,作用就是代表单链表的头
2. 每添加一个节点,就直接加到链表的最后
3. 创建一个辅助变量来遍历链表,找到链表的最后
4. 当到链表的最后时,将新增的节点直接加到temp.next

代码:

//向节点中增加数据、直接添加到链表的尾部
public void add(Node node){
    //因为head不能动,所以我们增加一个辅助遍历temp
    Node temp =head;
    while (true){
        if (temp.next==null){
            //如果temp的next等于空,则到了链表最后
            break;
        }
        //如果辅助节点的下一个不等于空,那么还有数据,令temp=他的子节点
        temp=temp.next;
    }
    //当退出while循环的时候,则temp已经指向链表的最后了
    temp.next=node;
}

3、第二种方式添加节点时,根据节点的no编号将节点插入指定位置

思路:

需要按找编号no的顺序来添加
1. 首先找到新添加的节点位置,当然还是用辅助变量(指针),来遍历找到改变位置的前一个。
2. 新的节点.next = temp.next 意思就是比他大的先接到新的节点next
3. 将temp.next = 新的节点 然后新的节点在指向temp的next

代码:

//在假设节点的序号需要排序,在插入的时候从小到大插入
public void addByOrder(Node node){
    //首先需要一个辅助节点
    Node temp = head;
    // 意思很简单,我们插入的节点的序号,大于前一个节点,小于下一个节点的序号
    boolean flag = false;
    while(true) {
        if(temp.next == null){
            //已经到链表最后了,说明前面没有比新节点大的
            break;
        }
        if(temp.next.no > node.no){
            //找到了,temp.no比node.no小。但temp.next.no比node.no大
            break;
        }else if (temp.next.no==node.no){
                //节点已经存在
                flag=true;
        }
        temp=temp.next;//遍历
    }
    if (flag){
        //节点已存在
        System.out.println("该编号的节点已经存在");
    }else {
        //插入链表中
        node.next=temp.next;
        temp.next=node;
    }
}

4、修改节点

思路:

和上面的根据no插入相似,也可以查temp.next 也可以查temp

1. 先找到节点,通过temp遍历
2. 当temp.next.no == node.no时,temp的下一个节点,就是我们需要改的

代码:

修改特定节点的数据,由于我们定义了no作为序号,和上面的特定位置的思路差不多,不同的是,我们不知道我们现在的链表是不是有序的,那么也没关系,我们只要找到 temp.next.no = node.no

public void update(Node node){
    if (head.next==null){
        //头节点的子节点,没有数据,则链表为空
        System.out.println("链表为空,没有数据~~~~~");
        return;
    }
    Node temp=head;
    while (true) {
        if (temp.next ==null){
            //没有找到我们需要改的位置
            break;
        }
        if (temp.next.no == node.no){
            //恭喜,找到了
            //那么如何替换我们的数据呢? 和新增类似,不同的是需要中间那个需要挤掉
            //令这个node.next=temp.next.next
            node.next =temp.next.next;
            temp.next=node;
            break;
        }
        temp=temp.next;
    }
}

5、删除节点

思路:

1. 通过一个辅助变量temp找到要删除的节点,注意是temp.next是我们要删的
2. 这样就可以令temp.next = temp.next.next 把中间的给卡掉
3. 被删除的这个节点,没有其他地方引用它,就会被垃圾gc

代码:

public void delete(Node node){
    //删除节点也很容易,找到我们删除节点的位置即no相等,如果找不到则直接放回
    Node temp =head;
    while (true) {
        if (temp.next==null){
            break;
        }
        if (temp.next.no==node.no){
            //找到节点。temp的子节点,就是我们需要删除的节点,
            // 那么,我们令temp的子节点的子节点等于temp的子节点,那么中间那个就被挤掉了
            temp.next=temp.next.next;
            break;
        }
        temp=temp.next;
    }
}

6、 遍历

思路:

​ 很简单,用一个辅助遍历temp,当temp.next=null就结束了

代码:

// 查。 遍历节点
public void list(){
    if (head.next==null){
        //头节点的子节点,没有数据,则链表为空
        System.out.println("链表为空,没有数据~~~~~");
        return;
    }
    //一样的思路,需要一个子节点
    Node temp = head;
    //依次打印出temp的子节点
    while (true){
        if (temp.next==null){
            //子节点不存在
            break;
        }
        //输出节点信息
        System.out.println(temp.next);
        temp=temp.next;
    }
}

2、双链表

就是有两个节点,一个next指向下一个节点,一个pre指向前一个节点

双链表

管理单向链表的缺点分析:

1)单向链表,查找的方向只能是一个方向,而双向链表可以向前或者向后查找

2)单向链表不能自我删除,需要靠辅助节点,而双向链表可以自我删除

分析双链表的遍历,添加,修改,删除。

1)遍历 ,和单向链表一样

2)添加,默认添加到双向链表最后

  1. 先找到双向链表的最后这个节点
  2. temp.next =newNode
  3. newNode = temp

3)修改思路和单向链表一样

4)删除

  1. 因为是单向链表,因此我们可以实现自我删除某一个节点
  2. 直接找到这个要删的节点temp
  3. temp.pre.next = temp.next 把temp卡掉
  4. temp.next.pre = temp.pre

整个代码:

public class DoubleLinkedList {
    private DoubleNode head = new DoubleNode(0,"");

    //1 直接加在链表的最后
    public void add(DoubleNode node){
        DoubleNode temp = head;
        while (true){
            if (temp.getNext()==null){
                //链表最后了
                break;
            }
            temp=temp.getNext();
        }
        //当退出while循环的时候,则temp已经指向链表的最后了
        temp.setNext(node);
        node.setPre(temp);
    }
    //按序号添加数据
    public  void addByOrder(DoubleNode node){
        DoubleNode temp = head;
        boolean flag =false;
        while (true) {
            if (temp.getNext()==null){
                //链表最尾部了
                break;
            }
            if (node.getNo()<temp.getNext().getNo()) {
                //找到节点
                break;
            } else if (temp.getNext().getNo()==node.getNo()){
                //节点已经存在
                flag=true;
            }
            temp=temp.getNext();
        }
        if (flag){
            //节点已存在
            System.out.println("该编号的节点已经存在");
        }else {
            //插入链表中
            if (temp.getNext()==null){
                temp.setNext(node);
                node.setPre(temp);
            }else{
                DoubleNode nextNode=temp.getNext();
                temp.setNext(node);
                node.setPre(temp);
                node.setNext(nextNode);
                nextNode.setPre(node);
            }
        }
    }
    //3 遍历双链表
    public void list(){
        if (head.getNext()==null){
            System.out.println("链表中没有数据");
            return;
        }
        DoubleNode temp = head;
        while (true){
            if (temp.getNext()==null){
                //子节点不存在
                break;
            }
            //输出节点信息
            System.out.println(temp.getNext());
            temp=temp.getNext();
        }
    }
    // 4 清空双链表
    public void  clear(){
        head.setNext(null);
    }
    //删除某一个节点
    public  void  delete(Integer no){
        if (head.getNext()==null){
            return;
        }
        DoubleNode temp = head.getNext();
        while (true){
            if (temp==null){
                //没找到
                break;
            }
            if (temp.getNo()==no){
                //找到要删除了
                temp.getPre().setNext(temp.getNext());
                temp.getNext().setPre(temp.getPre());
            }
            temp=temp.getNext();
        }
    }
    // 修改某一个节点
    public void update(DoubleNode node){
        if (head.getNext()==null){
            System.out.println("链表为空,没有数据~~~~~");
            return;
        }
        DoubleNode temp = head;
        while (true){
            if (temp.getNext()==null){
                //没找到
                break;
            }
            if (temp.getNext().getNo()==node.getNo()){
                //找到要修改的了
                node.setNext(temp.getNext().getNext());
                temp.setNext(node);
                break;
            }
            temp=temp.getNext();
        }
    }

}
class DoubleNode {
    private Integer no; //表示节点的序号
    private String name; //节点的名字
    private DoubleNode pre; // 指向前一个节点
    private DoubleNode  next; //指向下一个节点

    public DoubleNode(Integer no,String name){
        this.no=no;
        this.name=name;
    }

    @Override
    public String toString() {
        return "DoubleNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                '}';
    }
    //get set .......
}

3、环形链表

就是单链表的尾部节点指向头节点,形成一个环状

循环链表

其实就是单向链表中的最后一个节点.next=head

当循环链表只有一个节点的时候,就自己连自己

head.next=head

class CircleSingleLinkedList{
    //创建第一个first节点,当前没有编号
    private Boy first=null;
}
class Boy{
    private int no;//编号
    private Boy next; //指向下一个节点,默认null
    public Boy(int no){
        this.no=no;
    }
}

循环链表典型题目:Joseph问题。

2点多了,困了,下次和单链表的几个面试题目一起整理整理

9

评论区