一、特点

• 不占用连续存储空间
• 删除插入元素较方便
• 查询比较繁琐，需遍历链表元素

二、基本操作演示

// 向链表的尾部插入一个元素
public void addOne(int data)
// 删除链表中第index个元素
public boolean deleteNode(int index)
// 得到链表长度
public int length()
// 将链表中元素排序，返回排序后的链表头指针
public Node sortList()

import java.util.Stack;

/**
 * 
 * <p>
 * Description: 链表
 * </p>
 * 
 * @author
 * @date 2018-3-30
 * @version 1.0
 */
public class MyLinkedList {
    // 头指针
    Node head = null;

    // 尾插法：向链表的尾部插入一个元素
    public void addOne(int data) {
        Node newNode = new Node(data);
        if (isEmpty()) {
            head = newNode;
        } else {
            Node cur = head;
            while (cur.next != null) {
                cur = cur.next;
            }
            cur.next = newNode;
        }
    }

    /**
     * 判断链表是否为空
     * @return
     */
    public boolean isEmpty() {
        return head == null;
    }

    /**
     * 删除链表中第index个元素 
     * @param index：从1开始
     * @return
     */
    public boolean deleteNode(int index) {
        // 链表为空
        if (isEmpty()) {
            return false;
        }
        // 删除元素位置不合理
        if (index <= 0 || index > length()) {
            return false;
        }
        if (index == 1) {
            head = head.next;
            return true;
        } else {
            Node pre = head;
            Node cur = head.next;
            // 当前正在判断的节点
            int i = 2;
            // 从链表的第二个元素开始遍历
            while (cur != null) {
                if (index == i) {
                    pre.next = cur.next;
                    return true;
                }
                pre = cur;
                cur = cur.next;
                i++;
            }
            return false;
        }
    }

    // 得到链表长度
    public int length() {
        // 遍历链表
        int count = 0;
        Node cur = head;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }

    // 将链表中元素排序，返回排序后的链表头指针
    public Node sortList(){
        return null;
    }
    
    /**
     * 从头结点开始打印链表
     */
    public void print(){
        Node cur=head;
        while(cur!=null){
            System.out.print(cur.data+" ");
            cur=cur.next;
        }
        System.out.println();
    }
    
    /**
     * 借助栈：逆序输出栈中元素
     */
    public void reversePrint_stack() {
        Stack<Integer> ms = new Stack<Integer>();
        Node cur = head;
        while (cur != null) {
            ms.push(cur.data);
            cur = cur.next;
        }
        for (int i = ms.size() - 1; i >= 0; i--) {
            Integer item = ms.get(i);
            System.out.print(item.toString() + " ");
        }
        System.out.println();
    }

    /**
     * 利用递归：逆序输出栈中元素
     */
    private void reversePrint_recursion() {
        reversePrintStack(head);
        System.out.println();
    }
    
    private void reversePrintStack(Node head) {
        if (head == null) {
            return;
        }
        reversePrintStack(head.next);
        System.out.print(head.data + " ");
    }
    
    class Node {
        // 数据域
        int data;
        // 指针域
        Node next;

        public Node(int data) {
            this.data = data;
            this.next = null;
        }
    }
    
    public static void main(String[] args) {
        MyLinkedList l=new MyLinkedList();
        l.addOne(1);
        l.addOne(2);
        l.addOne(3);
        l.addOne(4);
        // 从头结点开始顺序输出
        l.print();
        l.deleteNode(1);
        l.print();
        // 逆序输出
        l.reversePrint_stack();
        l.reversePrint_recursion();
    }
}