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

2018-06-18 00:40:05来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

原理来自百度百科 

一、链表的定义

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

链表与线性表的区别:

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();
    }
}

 

三、双向链表

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

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:java 数据结构与算法---递归

下一篇:Mybatis学习笔记之二(动态mapper开发和spring-mybatis整合)