一、链表的定义
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。
链表与线性表的区别：
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(); } }
三、双向链表
双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。
原创文章，作者：Maggie-Hunter，如若转载，请注明出处：https://blog.ytso.com/tech/pnotes/16292.html