数据结构链表——用Java实现无头单向不循环链表（接口的定义和接口的实现）

约定不等于承诺〃 2023-06-10 05:25 31阅读 0赞

1，接口的定义

public interface ILinked {
        
        //头插法
        void addFirst(int date);
        //尾插法
        void addLast(int date);
        //在任意位置插入，第一个数据节点为0号下标
        boolean addindex(int index,int date);
        //查找是否包含key在单链表中
        boolean contains(int key);
        //删除key第一次出现的节点
        int remove(int key);
        //删除所有值为key的节点
        void removeAllKey(int key);
        //得到单链表的长度
        int getLength();
        void display();
        void clear();
    }

2，实现接口的类

package mySingLeListImpl;
    
    import impl.ILinked;
    
    
    public class MySingleListImpl implements ILinked {
        
         class Node {
        
            private int date;
            private Node next;
            private Node(int date) {
        
                this.date = date;
                this.next = null;
            }
        }
        private Node head;
        public MySingleListImpl() {
        
    
            this.head = null;
        }
        @Override
        public void addFirst(int date) {
        
            Node node = new Node(date);
            if (this.head ==null) {
        
                this.head = node;
            }else {
        
                node.next = this.head;
                this.head = node;
            }
    
        }
    
        @Override
        public void addLast(int date) {
        
          Node node = new Node(date);
          Node cur = this.head;
          if (this.head == null) {
        
              this.head = node;
          }else {
        
             while(cur.next!=null) {
        
                 cur = cur.next;
             }
             cur.next = node;
          }
        }
    
        @Override
        public boolean addindex(int index, int date) {
        
            if(index < 0 || index > getLength()) {
        
                throw new IndexOutOfBoundsException("下标不合法");
            }
            Node node = new Node(date);
            Node cur = this.head;
            if (this.head == null) {
        
                this.head = node;
            }else {
        
                int count = 0;
                while (count < index-1 ) {
        
                    cur = cur.next;
                    count++;
                }
                node.next = cur.next;
                cur.next = node;
            }
            return false;
        }
    
        @Override
        public boolean contains(int key) {
        
         Node node = this.head;
         while (node != null) {
        
             if (node.date == key) {
        
                 return true;
             }
             node = node.next;
         }
            return false;
        }
    
        @Override
        public int remove(int key) {
        
            if (contains(key)){
        
                Node node = this.head;
                if (this.head.date == key) {
        
                    node = node.next;
                    this.head = null;
                    this.head = node;
                    return 1;
                }
                while (node.next.date!= key ) {
        
                    node = node.next;
                }
                node.next = node.next.next;
                return 1;
            }else {
        
                System.out.println("该数不存在！");
            }
            return 0;
        }
    
        @Override
        public void removeAllKey(int key) {
        
            while (contains(key)) {
        
                remove(key);
            }
            System.out.println("全部删除！");
        }
    
        public void removeAllKey1(int key) {
        
            Node pre = this.head;
            Node cur = this.head.next;
            while (cur != null) {
        
                if (cur.date == key) {
        
                    pre.next = cur.next;
                    cur = pre.next;
                } else {
        
                    pre = cur;
                    cur = cur.next;
                }
    
            }
            if (this.head.date == key) {
        
                this.head = this.head.next;
            }
        }
    
    
        @Override
        public int getLength() {
        
            int count = 0;
            if (this.head == null) {
        
                return count;
            }else {
        
                count++;
                Node node = this.head;
                while (node.next !=null) {
        
                    count++;
                    node = node.next;
                }
            }
            return count;
        }
    
        @Override
        public void display() {
        
            if (this.head == null) {
        
                System.out.println("链表为空！");
            }else {
        
                Node node = this.head;
                while (node != null) {
        
                    System.out.print(node.date + " ");
                    node = node.next;
                }
                System.out.println();
            }
        }
    
        @Override
        public void clear() {
        
            while(this.head != null) {
        
                Node node = this.head.next;
                this.head = null;
                this.head = node;
            }
        }
    }

3，测试类

import mySingLeListImpl.MySingleListImpl;
    
    public class TestMySingleListImpl {
        
        public static void main(String[] args) {
        
            MySingleListImpl mySingleList = new MySingleListImpl();
            mySingleList.addFirst(1);
            mySingleList.addLast(2);
            mySingleList.display();
            mySingleList.addindex(2,1);
            mySingleList.display();
            mySingleList.removeAllKey(1);
            mySingleList.display();
            if (mySingleList.remove(2) == 1) {
        
                System.out.println("删除成功！");
            }
            mySingleList.display();
            System.out.println("长度："+ mySingleList.getLength());
            mySingleList.clear();
            mySingleList.display();
        }
    }

4，运行结果

1 2 
    1 2 1 
    全部删除！
    2 
    删除成功！
    链表为空！
    长度：0
    链表为空！