本人微信公众号"aeolian"~

数据结构之链表基本操作

数据结构有八大类

  • 1、数组
  • 2、栈
  • 3、队列
  • 4、链表
  • 5、树
  • 6、散列表
  • 7、堆
  • 8、图

 链表基本操作:头位置添加、头位置删除、任意位置添加、任意位置删除、根据下标查找节点、根据数据查找节点、获取长度、打印所有节点

package com.autumn.LinkedList;

/**
 * 节点
 */
class Node{
    private String data;   //包含数据
    private Node next;   //指针域,下一个节点,因为对象为引用类型所以在内存中此next变量指向内存中的另一个Node
    public String getData() {
        return data;
    }
    public void setData(String data) {
        this.data = data;
    }
    public Node getNext() {
        return next;
    }
    public void setNext(Node next) {
        this.next = next;
    }

    public Node() {
    }

    //显示当前节点
    public void display(){
        System.out.println("当前节点数据:"+data);
    }
}
public class LinkedList {
    public Node header = null;

    /**
     * 获取长度
     * @param header 头节点
     * @return
     */
    public static int getListLength(Node header){
        int len = 0;
        while (header!=null){  //判断当前节点是否存在
            len++;  //当前节点存在,长度加一
            header = header.getNext();  //将下一个节点赋给当前节点,当末节点getNext()时,返回为null
        }
        return len;
    }

    /**
     * 添加节点,在头位置添加节点
     * @param headNode 头节点
     * @param newNode 新增节点
     * @return 返回新的链表头节点
     */
    public static Node addNode(Node headNode,Node newNode){
        newNode.setNext(headNode);   //新节点设置为头
        return newNode;  //返回新的头结点引用
    }

    // 删除一个头结点,并返回头结点
    public static Node delNode(Node headNode) {
        Node temp = null;
        temp = headNode.getNext();
        headNode = null;   //将删除的节点置为null
        return temp;
    }

    /**
     * 在任意位置插入节点 在index的后面插入
     * @param header  链表头
     * @param index  下标 从0开始 ,为null时加在链表尾部
     * @param data 节点数据
     */
    public static void add(Node header,Integer index, String data) {
        //新建节点
        Node newNode = new Node();
        newNode.setData(data);
        if (index==null){  //当位置为null时
            index = getListLength(header);   //长度设为index下标
        }

        Node current = header;   //当前节点
        Node previous = null;   //上一个节点
        int pos = 0;   //位置下标
        while (pos != index&¤t!=null) {   //遍历位置下标,且当前节点不为null,当为null时上一个节点为末节点
            previous = current;   //当前->上节点
            current = current.getNext();  //获取当前节点
            pos++;  //下标++
        }
        if (current==null){   //为null时是因为当前为null,上一个节点即是最后一个节点
            previous.setNext(newNode);
        }else{
            previous.setNext(newNode);
            newNode.setNext(current);
        }
    }

    /**
     * 删除指定位置节点
     * @param header 链表头
     * @param index 删除的下标,为null时删除末节点
     * @return 返回新链表的头节点
     */
    public static Node del(Node header,Integer index) {
        if (index==null){  //当位置为null时
            index = getListLength(header)-1;   //长度设为index下标即最后一个
        }

        Node current = header;   //当前节点
        Node previous = null;   //上一个节点
        int pos = 0;   //位置下标
        while (pos != index&¤t!=null) {   //遍历位置下标,且当前节点不为null,当为null时上一个节点为末节点
            previous = current;   //当前->上节点
            current = current.getNext();  //获取当前节点
            pos++;  //下标++
        }
        if (current==null){   //为null时是因为当前为null,上一个节点即是最后一个节点
            System.out.println("无法删除第"+index+"节点,总长度为"+getListLength(header));
        }else{
            if (current.getNext()==null){   //当current正好是最后一个节点
                previous.setNext(null);   //上一个节点的指针域指向null
                current = null;  //要删除的设为null
            }else if(pos==0){         //当要删除的是第一个时
                Node newHead = current.getNext();
                current = null; //要删除的设为null
                return newHead;   //返回下一个节点为头节点
            }else {   //当要删除的节点有上一个和下一个时
                previous.setNext(current.getNext());   //上一个节点的指针域指向当前节点的指向
            }
        }
        return header;
    }

    /**
     * 删除指定数据的节点
     * @param data
     * @return
     */
    public static Node deleteByData(Node header, String data) {
        Node current = header;
        Node previous = null;
        while(current!=null&&!current.getData().equals(data)){   //当节点数据域不等于指定数据时循环
            previous = current;
            current = current.getNext();
        }
        if(current==null){   //遍历到最后未找到
            System.out.println("删除失败,未找到"+data);
        }else if (previous==null){   //删除的current为第一个节点
            if (current.getNext()==null){   //要删除的头节点为末节点,即此链表只有一个节点
                current = null;
                System.out.println("此节点只有一节点,删除完毕,返回null");
                return null;
            }else {   //要删除的头节点不为末节点,即此节点数大于二
                return current.getNext();
            }
        }else if (current.getNext()==null){   //删除的current为末节点
            previous.setNext(null);
            current = null;
            return header;
        }else {   //不为首也不为末
            previous.setNext(current.getNext());
            return header;
        }
        return null;
    }

    // 根据位置查找节点信息
    public static Node findByPos(Node header, int index) {
        Node current = header;
        int pos = 0;
        while (pos != index&¤t!=null) {
            current = current.getNext();
            pos++;
        }
        if (current == null){
            System.out.println("无此节点,index:"+index);
            return null;
        }
        System.out.println("第"+index+"节点的数据为"+current.getData());
        return current;
    }

    // 根据数据查找节点信息
    public static Node findByData(Node header, String data) {
        Node current = header;
        while (current.getData() != data) {
            if (current.getNext() == null)   //当前节点为末节点,则未找到
            {
                System.out.println("无此节点,data:"+data);
                return null;
            }
            current = current.getNext();
        }
        System.out.println(""+current+"节点的数据为"+current.getData());
        return current;
    }


    /**
     * 打印所有节点
     * @param header 头节点
     */
    public static void displayAllNode(Node header){
        while(header!=null){
            header.display();
            header = header.getNext();
        }
    }

    public static void main(String[] args) {
        Node nodeFirst = new Node();
        nodeFirst.setData("第一个节点的数据");
        Node nodeSec = new Node();
        nodeSec.setData("第二个节点的数据");
        nodeFirst.setNext(nodeSec);   //第一个节点指向第二个
        Node nodeThird = new Node();
        nodeThird.setData("第三个节点的数据");
        nodeSec.setNext(nodeThird);   //第二个节点指向第三个节点
        Node nodeFour = new Node();
        nodeFour.setData("第四个节点的数据");
        nodeThird.setNext(nodeFour);   //第三个节点指向第四个节点
        int len = getListLength(nodeFirst);
        System.out.println("当前节点长度为"+len);

        //添加新节点
        /*Node newNode = new Node();
        newNode.setData("this is a new node");
        nodeFirst = addNode(nodeFirst,newNode); */

        //删除节点
        //nodeFirst = delNode(nodeFirst);

        //添加指定位置的节点
        //add(nodeFirst,null,"this is a new node");

        //删除指定位置节点
        //nodeFirst=del(nodeFirst,0);

        //删除指定数据的节点
        //nodeFirst = deleteByData(nodeFirst, "第一个节点的数据");

        //根据位置查找节点
        Node result_findByPos = findByPos(nodeFirst,0);

        //根据内容查找节点
        Node result_findByData = findByData(nodeFirst,"第一个节点的数据");


        System.out.println("打印所有节点:");
        displayAllNode(nodeFirst);

    }
}

 

 

初次错误写法,在方法中进行对象的引用操作,想把headNode直接赋值为新的头结果

    /**
     * 添加节点,在头位置添加节点
     * @param headNode 头节点
     * @param newNode 新增节点
     * @return 返回新的链表头节点
     */
    public static void addNode(Node headNode,Node newNode){
        newNode.setNext(headNode);   //新节点设置为头
        System.out.println("头结点位置headNode:"+headNode+"     新节点位置newNode"+newNode);
        headNode=newNode;   //无效,传递过来的headNode是个引用,可以改引用的对象里面的数据.但是!!!如果更改引用地址,则操作只在栈中操作,而栈在执行完方法时会自动销毁
        System.out.println("头结点位置headNode:"+headNode+"     新节点位置newNode"+newNode);  //赋值成功,但是返回的依然没用
    }
    // 删除一个头结点,并返回头结点
    public static void delNode(Node headNode) {
        headNode = headNode.getNext();   //无效,道理同addNode(),改变引用地址,并不是改变引用地址指向对象的内容
    }

调用

《数据结构之链表基本操作》

结果

《数据结构之链表基本操作》

 

 

参考:

https://www.cnblogs.com/CherishFX/p/4608880.html

点赞

Leave a Reply

Your email address will not be published. Required fields are marked *