JAVA链表操作

秒速五厘米 2022-04-24 11:42 190阅读 0赞

***数据结构学习***

## 建立单链表节点类 ##

package com.qcby.data;
    
    public class Node {
      private int data; //数据域
      private Node next; //指针域
    
      public Node(int data) {
          this.data = data;
      }
    
    public int getData() {
          return data;
      }
    
      public void setData(int data) {
          this.data = data;
      }
    
      public Node getNext() {
          return next;
      }
    
      public void setNext(Node next) {
          this.next = next;
      }
      //显示该结点的数据
      public void display() {
          System.out.print( "["+data + "]  ");
      }
    }

## 建立单链表类 ##

package com.qcby.data;
    
    public class SLinkList {
        private Node head;//表头
        private int length = 0;//获取链表的长度（结点的个数）
     
        public SLinkList() {
            this.head = null;
        }
     
    //在链表头部添加结点
        public void addHead(int data) {
            Node newNode = new Node(data);
            if(head == null){
                head = newNode;
                }
            else{
                newNode.setNext(head);
                head = newNode;
            }
            length++;//结点个数加1
        }
     
    //在链表头部删除结点
        public Node deleteHead() {
            if(head == null){
                return head;
            }
            Node curNode = head;//把头节点赋给curNode
            head = curNode.getNext();//把之前头节点指向的下一个节点置为新头
            length--;//结点个数减1
            return curNode;
        }
     
    //在链表尾部添加结点
        public void addTail(int data) {
            Node newNode = new Node(data);
            if (head == null) {
                head = newNode;
            } else {
                Node pre = head;
                int count = 1;
                while (count < length) {
                    pre = pre.getNext();
                    count++;
                }
                Node curNode = pre.getNext();//最后结点的next指针，即指向null
                newNode.setNext(curNode);//新结点的next指针指向最后结点的next指针
                pre.setNext(newNode);//最后结点的next指针指向新结点
            }
            length++;//结点个数加1
        }
     
    //在链表尾部删除结点
        public Node deleteTail() {
            if(head == null){
                return head;
            }
            Node preNode = head;
            int count = 1;
            while(count < length-1) {
                preNode = preNode.getNext();
                count++;
            }
            Node curNode = preNode.getNext();//指向最后一个结点
            preNode.setNext(curNode.getNext());//指向最后一个结点next指针值null
            length--;
            return null;
        }
    
     
    //在指定位置插入结点
        public void insertList(int data, int index) {
            Node newNode = new Node(data);
            if(head == null){
                head = newNode;//链表为空，插入
            }
            if(index > length+1 || index < 1) {
                System.out.println("结点插入的位置不存在，可插入的位置为1到"+(length+1));
            }
            if(index == 1) {
                newNode.setNext(head);
                head = newNode;//在链表开头插入
            }
            else{             //在链表中间或尾部插入                                
                Node preNode = head;
                int count = 1;
                while(count < index-1) {
                    preNode = preNode.getNext();
                    count++;
                }
                Node curNode = preNode.getNext();
                newNode.setNext(curNode);
                preNode.setNext(newNode);
            }
            length++;
        }
     
    //在指定位置删除结点
        public Node deleteList(int index) {
            if(index > length || index < 1) {
                System.out.println("结点删除的位置不存在，可删除的位置为1到"+length);
            }
            if(index == 1) {     //删除表头结点
                Node curNode = head;
                head = curNode.getNext();
                length--;
                return curNode;
            }
            else{         //删除链表中间或尾部结点
                Node preNode = head;
                int count = 1;
                while(count < index-1) {
                    preNode = preNode.getNext();
                    count++;
                }
                Node curNode = preNode.getNext();
                preNode.setNext(curNode.getNext());
                length--;
                return curNode;
            }
        }
     
    
     
    //获取指定位置的数据
        public void getIndexData(int index) {
            if(head == null){
                System.out.println("空表");
            }
            if(index > length || index < 1) {
                System.out.println("结点位置不存在，可获取的位置为1到"+length);
            }
            Node curNode = head;
            int count =1;
            while(count != index) {
                curNode =curNode.getNext();
                count++;
            }
            curNode.display();//显示该位置的结点数据
            System.out.println();
        }
     
    //修改指定位置的结点数据，与获取指定位置的数据的方法基本一致。
        public void updateIndexData(int index, int data) {
            if(head == null){
                System.out.println("空表");
            }
            if(index > length || index < 1) {
                System.out.println("结点位置不存在，可更新的位置为1到"+length);
            }
            Node curNode = head;
            int count =1;         //也可以用for循环方式求取
            while(count != index) {
                curNode =curNode.getNext();
                count++;
            }
            curNode.setData(data);//将获取的指定位置的数据修改为指定的数据
        }}

## 建立双向链表节点类 ##

package com.qcby.data;
    
    //创建一个双向链表结点类，并用get，set方法获取其数据。
    public class DNode {
      private int data;//数据域
      private DNode next;//后继指针域
      private DNode previous;//前驱指针域
    
      public DNode(int data) {
          this.data = data;
          this.next = null;
          this.previous = null;
      }
    
      public int getData() {
          return data;
      }
    
      public void setData(int data) {
          this.data = data;
      }
    
      public DNode getNext() {
          return next;
      }
    
      public void setNext(DLLNode next) {
          this.next = next;
      }
    
      public DNode getPrevious() {
          return previous;
      }
    
      public void setPrevious(DLLNode previous) {
          this.previous = previous;
      }
      //显示该结点的数据
      public void display() {
          System.out.print( ”[“+data + "]   ");
      }
    }

## 建立双向链表类 ##

package com.qcby.data;
    
    public class DLinkList {
        private DNode head;//表头
        private int length = 0;
     
        public DLinkList() {
            this.head = null;
        }
     
        //在链表头部添加结点
        public void addHead(int data) {
            DNode newNode = new DNode(data);
            if(head == null) {
                head = newNode;//如果链表为空，增加新结点
            }
            else {
                newNode.setNext(head);
                head.setPrevious(newNode);
                head = newNode;
            }
            length++;
        }
     
        //在链表头部删除结点
        public void deleteHead() {
            if(head == null){
                System.out.println("空表，删除的结点不存在");
            }
            else {
                DNode curNode = head;
                head = curNode.getNext();
                head.setPrevious(null);
            }
            length--;
        }
     
        //在链表尾部添加结点
        public void addTail(int data) {
            DNode newNode = new DNode(data);
            if (head == null) {
                head = newNode;
            } else {
                DNode curNode = head;
                int count = 1;
                while (count < length) {
                    curNode = curNode.getNext();
                    count++;
                }
                newNode.setNext(null);
                newNode.setPrevious(curNode);
                curNode.setNext(newNode);
            }
            length++;
        }
     
        //在链表尾部删除结点
        public void deleteTail() {
            if(head == null){
                System.out.println("空表，删除的结点不存在");
            }else{
                DNode preNode = head;
                int count = 1;
                while(count < length-1) {
                    preNode = preNode.getNext();
                    count++;
                }
                preNode.setNext(null);
            }
            length--;
        }
     
    
     
     
        //在指定位置插入结点
        public void insertList(int data, int index) {
            DNode newNode = new DNode(data);
            if(head == null){
                head = newNode;//链表为空，插入
            }
            if(index > length+1 || index < 1) {
                System.out.println("结点插入的位置不存在，可插入的位置为1到"+(length+1));
            }
            if(index == 1) {
                newNode.setNext(head);
                head.setPrevious(newNode);
                head = newNode;//在链表开头插入
            } else{              //在链表中间或尾部插入
                DNode preNode = head;
                int count = 1;
                while(count < index-1) {
                    preNode = preNode.getNext();
                    count++;
                }
                DNode curNode = preNode.getNext();
                newNode.setNext(curNode);
                newNode.setPrevious(preNode);
                preNode.setNext(newNode);
             
                    curNode.setPrevious(newNode);
              
            }
            length++;
        }
     
        //在指定位置删除结点
        public void deleteList(int index) {
            if(index > length || index < 1) {
                System.out.println("结点删除的位置不存在，可删除的位置为1到"+length);
            }
            if(index == 1) {
                DNode curNode = head;
                head = curNode.getNext();
                head.setPrevious(null);
                length--;
            } else{
                DNode preNode = head;
                int count = 1;
                while(count < index-1) {
                    preNode = preNode.getNext();
                    count++;
                }
                DNode curNode = preNode.getNext();
                DNode laterNode = curNode.getNext();
                preNode.setNext(laterNode);
                if(laterNode != null) {  //若被删除结点的后继结点不是null结点，那么设置其前驱结点
                    laterNode.setPrevious(preNode);//指针指向被删除结点的前驱结点
                }
                length--;
            }
        }
        //获取指定位置的数据，与单链表一样
        public void getIndexData(int index) {
            if(head == null){
                System.out.println("空表");
            }
            if(index > length || index < 1) {
                System.out.println("结点位置不存在，可获取的位置为1到"+length);
            }
            DNode curNode = head;
            int count =1;
            while(count != index) {
                curNode =curNode.getNext();
                count++;
            }
            curNode.display();
            System.out.println();
        }
     
        //修改指定位置的结点数据，与单链表一样
        public void updateIndexData(int index, int data) {
            if(head == null){
                System.out.println("空表");
            }
            if(index > length || index < 1) {
                System.out.println("结点位置不存在，可更新的位置为1到"+length);
            }
            DNode curNode = head;
            int count =1;//while也可以用for循环方式解决
            while(count != index) {
                curNode =curNode.getNext();
                count++;
            }
            curNode.setData(data);
        }
    }