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

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

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实现。