java 数据结构与算法---链表
2024-08-20 12:05:45
原理来自百度百科
一、链表的定义
链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。
链表与线性表的区别:
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();
}
}
三、双向链表
双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。
最新文章
- java提高篇(二二)---LinkedList
- Linux shell if [ -n ] 正确使用方法
- mysql 查询某个日期时间段,每天同一时间段的数据
- dedecms代码研究六
- YARN的 AM与RM通信,申请资源分配过程
- ccnu-线段树-单点更新3-C
- 《MFC游戏开发》笔记三 游戏贴图与透明特效的实现
- osg
- 静态链表实现 (A-B)U(B-A)
- 五 Struts 配置文件
- Prometheus监控学习笔记之Prometheus从1.x升级到2.x
- SQL触发器批量删除数据库中的表
- c语言编程上次输入影响下次记过怎么解决要交作业啦求大神相助
- C/S 开发框架 ----- 广州本地
- node基础知识-常用node命令
- 【洛谷】【单调队列】P2032 扫描
- 能帮我们学习吉他的音乐软件——Guitar Pro
- HTML - 分页效果布局
- Zend_Application 流程详解
- 设置视口中心点setViewCenter
热门文章
- <;link rel=";stylesheet"; type=";text/css"; href=";css/index.css";>;详解
- JetBrains全家桶使用攻略
- Magic Trackpad 2 on win10 x64
- 微信小程序中的 web-view 组件
- 域名配置https
- load和loads的区别
- linux一切皆文件之Unix domain socket描述符(二)
- Python处理PDF和Word文档常用的方法(二)
- 阿里nas挂载错误
- excel中如何将时间戳转换为日期格式