线性表的链式存储实现(Java版)

拼搏现实的明天。 2022-12-18 15:49 135阅读 0赞

链表:一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

package algorithm.datastructure.linklist;
    import java.util.NoSuchElementException;
    
    /* * 链表 * 物理存储上非连续的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现 * * */
    public class LinkedList { 
        private Node head;//头节点
        private int size;//链表长度
        static private class Node{ 
            private int data;
            private Node next;
            public Node(){ 
    
            }
            private Node(int data,Node next){ 
                this.data=data;
                this.next=next;
            }
        }
    
        //初始化空链表
        public LinkedList(){ 
            //head=null;
        }
    
        //添加元素
        public Boolean add(int element){ 
            linkLast(element);
            return true;
        }
        //在某个位置之前添加元素
        public Boolean add(int index,Integer element){ 
            checkPositionIndex(index);
            if (index==size){ 
                linkLast(element);
            } else { 
                linkBefore(element,node(index));
            }
    
            return true;
        }
        //根据下标获取元素
        public int get(int index){ 
            checkElementIndex(index);
            return node(index).data;
        }
        //获取第一个元素
        public Integer getFirst(){ 
            Node f=head;
            if (f==null){ 
                throw new NoSuchElementException();
            }  else { 
                return f.data;
            }
        }
        //获取最后一个元素
        public Integer getLast(){ 
            if (size==0){ 
                throw new NoSuchElementException();
            }
            int index=size-1;
            return node(index).data;
        }
    
        //删除第一个元素
        public Integer removeFirst(){ 
            Node f=head;
            if (f==null){ 
                throw new NoSuchElementException();
            } else { 
                return unlink(head);
            }
        }
    
        //删除最后一个元素
        public Integer removeLast(){ 
            if (size==0){ 
                throw new NoSuchElementException();
            }
            int index=size-1;
            return unlink(node(index));
        }
    
    
        //根据索引删除元素
        public Integer remove(int index){ 
            checkElementIndex(index);
            return unlink(node(index));
        }
    
        //销毁链表
        public void destroyList(){ 
            clearList();
        }
        //将链表置为空表
        public void clearList() { 
    
            for (Node p=head;p!=null;){ 
                Node next=p.next;//记录下一个结点
                p=null;//删除当前结点
                p=next;//指向下一个结点
            }
            size=0;
            head=null;
        }
        //遍历链表
        public void traverseList(){ 
    
            for (Node p=head;p!=null;){ 
                System.out.println(p.data);
                p=p.next;
            }
        }
    
        //返回链表元素个数
        public int size(){ 
            return size;
        }
    
    
        //尾部添加结点
        private void linkLast(int element){ 
            Node cur =null,p;
            if (size==0){ //没有结点时
                head=new Node(element,null);
                size++;
                return;
            }
            for (p=head;p!=null;){ //有结点时候
                cur=p;
                p=cur.next;
            }
            cur.next= new Node(element,null);//尾部添加元素
            size++;
        }
    
    
        //在某结点之前插入结点
        private void linkBefore(int element,Node node){ 
            if (node==null){ 
                linkLast(element);
            } else { 
                Node p=head,q=p.next;
                if (node.data==p.data){ //node为结点时候
                    head= new Node(element, p);//在头部插入元素
                    size++;
                } else { 
                    while (p!=null){ 
                        if (q.data==node.data) { 
                            p.next= new Node(element,q);//在q之前(p之后)插入一个元素
                            size++;
                            break;
                        }
                        p=p.next;
                        q=p.next;
                    }
    
                }
            }
    
        }
    
        //删除结点
        private Integer unlink(Node node){ 
            Integer deleteNodeData=null;
            Node p=null;
            deleteNodeData=node.data;
            if (node.data==head.data){ //该节点为头结点
                p=head;
                head=p.next;
                p=null;
                size--;
            } else { 
                Node q=head;
                for (p=q.next;p!=null;){ //使用两个指针,p,q
                    if (p.data==node.data){ 
                        break;
                    }
                    q=q.next;//p始终为q的next结点
                    p=q.next;
                }
                q.next=p.next;
                p=null;//删除p
                size--;
            }
            return deleteNodeData;
        }
    
        //数组下标是否越界
        private Boolean isElementIndex(int index){ 
            return index>=0&&index<size;
        }
        //插入位置是否越界
        public Boolean isPositionIndex(int index){ 
            return index>=0&&index<=size;
        }
    
        //检验下标是否越界，抛出异常
        private void checkElementIndex(int index){ 
            if(!isElementIndex(index)){ 
                try { 
                    throw new IndexOutOfBoundsException("下标越界");
                } catch (Exception e) { 
                    e.printStackTrace();
                }
            }
        }
    
        //检验插入下标是否越界，抛出异常
        private void checkPositionIndex(int index){ 
            if(!isPositionIndex(index)){ 
                try { 
                    throw new IndexOutOfBoundsException("下标越界");
                } catch (Exception e) { 
                    e.printStackTrace();
                }
            }
        }
    
    
    
    
    
    
    
        //返回指定位置的元素
        private Node node(int index){ 
            int nowIndex = 0;
            if(size>0){ 
                for (Node p=head;p!=null;){ 
                    if (nowIndex==index){ 
                        return p;
                    }
                    p=p.next;
                    nowIndex++;
                }
            }
            return null;
    
        }
    
        public static void main(String[] args) { 
    
    
            java.util.LinkedList linkedList0=new java.util.LinkedList();
            linkedList0.add(6);
            linkedList0.remove(0);
            linkedList0.size();
            linkedList0.peek();
            //linkedList0.getFirst();
            linkedList0.clear();
    
            //测试
            LinkedList linkedList=new LinkedList();
            linkedList.add(2);
            linkedList.add(6);
            linkedList.add(0);
            linkedList.add(3);
            linkedList.add(8);
            linkedList.add(10);
            System.out.println(linkedList.get(0));
            System.out.println(linkedList.getFirst());
            System.out.println(linkedList.getLast());
            System.out.println(linkedList.get(5));
            System.out.println(linkedList.remove(5));
            System.out.println(linkedList.remove(4));
    
            linkedList.remove(2);
            linkedList.remove(0);
            linkedList.remove(0);
            linkedList.remove(0);
    
            linkedList.add(2);
            linkedList.add(6);
            linkedList.add(0);
            linkedList.add(3);
            linkedList.add(8);
            linkedList.add(10);
    
            linkedList.removeFirst();
            linkedList.removeFirst();
            linkedList.removeLast();
            System.out.println(linkedList.size());
    
    
            System.out.println("遍历链表");
            linkedList.traverseList();
            linkedList.add(0,4);
            linkedList.add(0,5);
            linkedList.add(2,5);
    
            linkedList.add(4,5);
    
            linkedList.add(6,9);
            linkedList.add(8,11);
            linkedList.add(9,222);
            // linkedList.linkBefore(3,new Node(3,null));
    // linkedList.linkBefore(3,new Node(2,null));
    // linkedList.linkBefore(3,new Node(2,null));
    // linkedList.linkBefore(7,new Node(2,null));
    // linkedList.linkBefore(9,new Node(7,null));
    // linkedList.linkBefore(9,new Node(8,null));
            System.out.println("遍历链表");
            linkedList.traverseList();
            linkedList.clearList();
    
    
    
        }
    }

以上就是Java简单实现线性表的链式存储，更多功能可参考Java集合中的LinkedList实现。