链表链表通常由一连串节点组成，每个节点包含任意的实例数据（data fields）和一或两个用来指向上一个/或下一个节点的位置的链接（"links"）（Linked list）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。
　　使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。
链表按照结构划分为单链表和双端链表， 按照元素的顺序分为有序链表和无序链表

1、单向链表（Single-Linked List）

单链表是链表中结构最简单的。一个单链表的节点(Node)分为两个部分，第一个部分(data)保存或者显示关于节点的信息，另一个部分存储下一个节点的地址。最后一个节点存储地址的部分指向空值。

单向链表只可向一个方向遍历，一般查找一个节点的时候需要从第一个节点开始每次访问下一个节点，一直访问到需要的位置。而插入一个节点，对于单向链表，我们只提供在链表头插入，只需要将当前插入的节点设置为头节点，next指向原头节点即可。删除一个节点，我们将该节点的上一个节点的next指向该节点的下一个节点。

image

在表头增加节点：

image

删除节点：

image

①、单向链表的具体实现

    package com.ys.datastructure;

    public class SingleLinkedList {
        private int size;//链表节点的个数
        private Node head;//头节点
        
        public SingleLinkedList(){
            size = 0;
            head = null;
        }
        
        //链表的每个节点类
        private class Node{
            private Object data;//每个节点的数据
            private Node next;//每个节点指向下一个节点的连接
            
            public Node(Object data){
                this.data = data;
            }
        }
        
        //在链表头添加元素
        public Object addHead(Object obj){
            Node newHead = new Node(obj);
            if(size == 0){
                head = newHead;
            }else{
                newHead.next = head;
                head = newHead;
            }
            size++;
            return obj;
        }
        
        //在链表头删除元素
        public Object deleteHead(){
            Object obj = head.data;
            head = head.next;
            size--;
            return obj;
        }
        
        //查找指定元素，找到了返回节点Node，找不到返回null
        public Node find(Object obj){
            Node current = head;
            int tempSize = size;
            while(tempSize > 0){
                if(obj.equals(current.data)){
                    return current;
                }else{
                    current = current.next;
                }
                tempSize--;
            }
            return null;
        }
        
        //删除指定的元素，删除成功返回true
        public boolean delete(Object value){
            if(size == 0){
                return false;
            }
            Node current = head;
            Node previous = head;
            while(current.data != value){
                if(current.next == null){
                    return false;
                }else{
                    previous = current;
                    current = current.next;
                }
            }
            //如果删除的节点是第一个节点
            if(current == head){
                head = current.next;
                size--;
            }else{//删除的节点不是第一个节点
                previous.next = current.next;
                size--;
            }
            return true;
        }
        
        //判断链表是否为空
        public boolean isEmpty(){
            return (size == 0);
        }
        
        //显示节点信息
        public void display(){
            if(size >0){
                Node node = head;
                int tempSize = size;
                if(tempSize == 1){//当前链表只有一个节点
                    System.out.println("["+node.data+"]");
                    return;
                }
                while(tempSize>0){
                    if(node.equals(head)){
                        System.out.print("["+node.data+"->");
                    }else if(node.next == null){
                        System.out.print(node.data+"]");
                    }else{
                        System.out.print(node.data+"->");
                    }
                    node = node.next;
                    tempSize--;
                }
                System.out.println();
            }else{//如果链表一个节点都没有，直接打印[]
                System.out.println("[]");
            }
            
        }

    }

测试：

    @Test
    public void testSingleLinkedList(){
        SingleLinkedList singleList = new SingleLinkedList();
        singleList.addHead("A");
        singleList.addHead("B");
        singleList.addHead("C");
        singleList.addHead("D");
        //打印当前链表信息
        singleList.display();
        //删除C
        singleList.delete("C");
        singleList.display();
        //查找B
        System.out.println(singleList.find("B"));
    }

打印结果：

image

双端链表

对于单项链表，我们如果想在尾部添加一个节点，那么必须从头部一直遍历到尾部，找到尾节点，然后在尾节点后面插入一个节点。这样操作很麻烦，如果我们在设计链表的时候多个对尾节点的引用，那么会简单很多。

image

注意和后面将的双向链表的区别！！！

①、双端链表的具体实现

    public class LinkedList<E> {
        /**
         * 结点
         */
        private static class Node<E> {
            E item;
            Node<E> prev;
            Node<E> next;

            public Node(Node<E> prev, E item, Node<E> next) {
                this.item = item;
                this.prev = prev;
                this.next = next;
            }
        }

        public LinkedList() {

        }

        //头节点
        Node<E> first;
        //尾节点
        Node<E> last;
        //大小
        int size;

        /**
         * 添加数据在最后
         */
        public void add(E e) {
            linkLast(e);
        }

        /**
         * 添加到最后
         * @param e
         */
        private void linkLast(E e) {
            Node<E> newNode = new Node<E>(last, e, null);
            Node<E> l = last;
            last=newNode;

            if(l==null){
                first=newNode;
            }else {
                l.next = newNode;
            }
            size++;
        }
        /**
         * 查找位置
         */
        public E get(int index){
            if(index<0 || index>size){
                return null;
            }
            return node(index).item;
        }
        /**
         * 获取index位置上的节点
         */
        private Node<E> node(int index){

            //如果index在整个链表的前半部分
            if(index<(size>>1)){   //1000 100   10
                Node<E> node=first;
                for (int i = 0; i < index; i++) {
                    node=node.next;
                }
                return node;
            }else{
                Node<E> node=last;
                for (int i = size-1; i > index; i--) {
                    node=node.prev;
                }
                return node;
            }


        }

        /**
         * 添加数据在index位置
         */
        public void add(int index,E e) {
            if(index<0 || index>size){
                return ;
            }
            if(index==size){
                linkLast(e);
            }else{
                Node<E> target=node(index);//  index=2
                Node<E> pre=target.prev;
                Node<E> newNode=new Node<E>(pre,e,target);

                if(pre==null){
                    first=newNode;
                    target.prev = newNode;//4
                }else {
                    pre.next = newNode;//3
                    target.prev = newNode;//4
                }
                size++;
            }

        }

        /**
         * 删除元素
         */
        public void remove(int index){
            Node<E> target=node(index);
            unlinkNode(target);
        }

        private void unlinkNode(Node<E> p) {//index=2
            Node<E> pre=p.prev;
            Node<E> next=p.next;
            if(pre==null){
                first=p.next;
            }else{
                pre.next=p.next;
            }
            if(next==null){
                last=p.prev;
            }else{
                next.prev=p.prev;
            }
            size--;
        }

    }