当前位置:   article > 正文

JAVA——链表_java链表

java链表

一、链表概念及结构

链表:链表是一种物理存储结构上非连续存储结构,数据元素的逻辑顺序是通过链表中的引用链接次序实现的。如下图:(通俗的说:就是由一个个节点组成,这些节点逻辑上连续,物理上不连续)

类比火车:

singleLinkedList ——火车车次(一整个火车or哪趟火车)

Node——车厢,具体储存元素的类,每个单链表的节点就是Node的一个对象

Node.head ;——当前链表的头节点(只要知道头节点就可以此访问链表中的所有节点)

int  size ;——当前链表的长度(节点个数),保存有效数据的个数

画图理解:

  1. class Node {
  2. int val ; //储存节点的值
  3. Node next ; //表示下一个节点的地址
  4. //这里为什么使用Node引用,单链表的所有节点都是Node类的对象
  5. }
  6. Node node = new Node();//创建一个新节点
  7. node.val =1 ;//值为1,地址为空,就没写
  8. //与其他节点进行连接
  9. Node node1 = new Node(); //创建名为node1的新节点
  10. node1.val = 2 ; //值为2
  11. node.next = node1 ;//让第一个结点的next储存下一个结点的地址

二、链表的实现方法 

※注意事项:

①单链表中头节点很烦人,不论是插入还是删除均需考虑头节点,因为其没有前驱。

②所有的点操作(".")均需注意空指针情况

2.1头插法

利用虚拟头节点的办法:

虚拟头节点:——dummyHead,只作为链表的头节点使用,不储存有效数据即size的长度没变,这样链表中的其他有效节点我们可以一视同仁,都有头节点

 

2.2在任意位置插入

利用虚拟头节点的办法:

2.3在链表尾部插入

2.4查找第一个值为val的值的索引

2.5查找是否包含val值

2.6查找索引为index位置的节点值

2.7将index位置的元素节点值修改为newVal

 2.8删除链表中第一个值为val的元素

2.9 删除链表中所有值为val的节点

 

利用虚拟头节点的方法:

2.10删除index位置的节点并返回该节点删除前的值

利用虚拟头节点的方法: 

 2.11删除头节点和尾节点

 

本文内容由网友自发贡献,转载请注明出处:【wpsshop博客】
推荐阅读
相关标签
  

闽ICP备14008679号