java 数据结构与算法---链表

原理来自百度百科 

一、链表的定义

　　链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

链表与线性表的区别：

1、由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多。
2、查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。
3、使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。

二、单向连表

　　单向链表（单链表）是链表的一种，其特点是链表的链接方向是单向的，对链表的访问要通过顺序读取从头部开始；链表是使用指针进行构造的列表；又称为结点列表，因为链表是由一个个结点组装起来的；其中每个结点都有指针成员变量指向列表中的下一个结点

 

package com.jalja.org.algorithm;

public class MyLink<E> {
    private Node<E> nowNode;//最近添加的Node
    private int size=0;//链表的个数
    
    //节点
    static class Node<E>{
        private E data;
        private Node<E> next;
        public Node(E e,Node<E> ne){
            this.data=e;
            this.next=ne;
        }
    }
    /**
     * 插入元素
     * @param e
     */
    public void insert(E e) {
        if(nowNode==null) {
            nowNode=new Node<E>(e,null); 
        }else {
            nowNode=new Node<E>(e,nowNode); 
        }
        size++;
    }
    /**
     * 按照指定位置插入元素
     * @param e
     * @param pos
     */
    public void insert(E e,int pos) {
        if(pos>size) {
            throw new RuntimeException("指定位置太大");
        }
        if(pos==0) {
            insert(e);
        }else {
            Node<E> now=nowNode;
            for(int i=0;i<pos-1;i++) {
                now=now.next;
            }
            Node<E> node=new Node<E>(e,now.next);
            now.next=node;
            size++;
        }
    }
    /**
     * 查找指定元素的节点
     * @param e
     * @return
     */
    public Node<E> find(E e){
        Node<E> now=nowNode;
        while(now!=null) {
            if(now.data.equals(e)) {
                break;
            }
            now=now.next;
        }
        
        return now;
    }
    /**
     * 删除指定元素
     * @param e
     */
    public void delete(E e) {
        Node<E> now=nowNode;//将要删除的Node
        Node<E> nowPrev=nowNode;//要删除元素的前一个Node
        while(now!=null) {
            if(now.data.equals(e)) {
                break;
            }
            nowPrev=now;
            now=now.next;
        }
        if(now==null) {
            throw new NullPointerException("指定元素不存在");
        }
        if(now==nowPrev) {
            nowNode=now.next;
        }else {
            nowPrev.next=now.next;
            now.next=null;
        }
        size--;
    }
    public void desplayAll() {
        Node<E> now=nowNode;
        while(now!=null) {
            System.out.println(now.data);
            now=now.next;
        }
    }
    public static void main(String[] args) {
        MyLink<String> link=new MyLink<String>();
        link.insert("A");
        link.insert("B");
        link.insert("C");
        
        link.desplayAll();
        
        link.insert("D", 0);
        
        link.delete("F");
        System.out.println("===================");
        link.desplayAll();
    }
}

 

三、双向链表

 　　双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。