-
2022-05-31 22:44:18
Background
最近在LeetCode上刷题时看到一道从尾到头打印链表的题,发现对链表的构建及遍历掌握不够,于是查找相关资料并对学习内容进行记录。
链表的基本结构
public class ListNode { int val; //结点数据 ListNode next; //指向下一个结点对象 }
在当前结构中添加构造方法,便于对链表进行初始化。
public class ListNode { int val; ListNode next; ListNode(int val){ this.val = val; } }
构建链表
构建链表的方法与C相似,其基本思想是:
- 创建头结点head并初始化(本次构建中head头结点也包含数据)
- 创建一个新结点nextNode指向当前头结点
- 循环遍历数据,每次循环创建一个结点接收当前数据,并使用nextNode.next指向当前新建结点,同时将nextNode结点指向像一个结点。
具体代码如下:
/** * 函数名称:createList * 函数功能:创建链表 */ // @Test public ListNode createList(){ ListNode head = new ListNode(0); //创建头结点 ListNode nextNode; nextNode = head; //循环遍历列表,并创建结点 for (int i = 0;i < 5;i++) { ListNode node = new ListNode(i); nextNode.next = node; nextNode = nextNode.next; } return head; }
遍历链表
遍历链表方法其实很简单,就是从头结点出发开始遍历,当指向的结点为空时停止遍历,说明此时链表已经遍历完成。
/** * 函数名称:print * 函数功能:打印链表 * @param head */ public void printLinkedList(ListNode head){ while(head != null){ System.out.print(head.val); head = head.next; } System.out.println(); }
更多相关内容 -
java链表方法
2018-04-25 08:51:44//使用clear()方法删除链表中的元素 LinkedList<Integer> list = new LinkedList<Integer>(); list.add(1); list.add(2); list.add(3); list.add(4); list.add(5);...//使用clear()方法删除链表中的元素 LinkedList<Integer> list = new LinkedList<Integer>(); list.add(1); list.add(2); list.add(3); list.add(4); list.add(5); System.out.println(list); list.subList(2,4).clear(); System.out.println(list);
使用 top() 和 pop() 方法来获取链表的元素
import java.util.LinkedList; public class Test { private static LinkedList list = new LinkedList(); public static void push(Object o){ list.addFirst(o); } public static Object top(){ return list.getFirst(); } public static Object pop(){ return list.removeFirst(); } public static void main(String[] args) { for (int i = 0; i < 10; i++) { list.push(i); } System.out.println(top()); System.out.println(pop()); System.out.println(pop()); System.out.println(pop()); }
使用 Collections 类的 sort() 方法对向量进行排序并使用 binarySearch() 方法来获取向量元素的索引值:
public static void main(String[] args) { Vector v = new Vector(); v.add("A"); v.add("E"); v.add("D"); v.add("P"); v.add("G"); Collections.sort(v); System.out.println(v); System.out.println(" D index : " + Collections.binarySearch(v, "D")); }
-
java 中链表的定义与使用方法
2020-08-31 00:43:11主要介绍了java 中链表的定义与使用方法的相关资料,需要的朋友可以参考下 -
Java中链表(Linked list)用法(单链表,双链表)
2022-03-07 16:39:21Java中链表的用法1.链表的概念2.链表的操作3.Java中链表的使用Java中链表的用法
1.链表的概念
- 链表是一种动态数据结构,他的特点是用一组任意的存储单元(可以是连续的,也可以是不连续的)存放 数据元素。
- 链表中每一个元素成为 “结点” , 每一个结点都是由数据域和指针域组成的, 每个结点中的指针域指向下一 个结点。
- Head 是 “头指针” , 表示链表的开始, 用来指向第一个结点, 而最后一个指针的指针域为 NULL( 空地址 ) ,表示链表的结束。
- 可以看出链表结构必须利用指针才能实现,即一个结点中必须包含一个指针变量,用来存放下一个结点的 地址。 实际上,链表中的每个结点可以用若干个数据和若干个指针。
单链表:结点中只有一个指针的链表称为单链表,这是最简单的链表结构。
其节点由两部分构成:- data域:数据域,用来存储元素数据
- next域:用于指向下一节点
双链表:有前后两个指针的链表。
其节点由三部分构成:- data域:数据域,用来存储元素数据
- next域:用于指向后一节点
- front域:用于指向前一节点
2.链表的操作
2.1 单链表的操作
2.1.1 插入节点
单链表插入节点主要分两步,顺序不可替换:
1.先将x->next指向A2
2.再将A1->next指向x
2.1.2 删除节点
删除节点其实只需要一步
A1->next 指向A3就行,此时A2会被自动回收
2.1.3 单链表的缺点
通过对单链表的分析,可以看出单链表有如下缺点:
- 单链表的查找方法只能是一个方向
- 单链表不能自我删除,需要靠上一节点进行辅助操作。
2.2 双链表的操作
2.2.1 插入节点
双链表的操作会比单链表复杂很多,顺序也可以是2143,其他的可以自己想一想,只要不断就行。
- x->next指向A2
- A1->next指向x
- x->prev指向A1
- A2->prev指向x
2.2.2 删除节点
删除节点容易很多,先后顺序也不是很重要
A3->prev指向A1
A1->next指向A3
3.Java中链表的使用
以下内容参考Java LinkedList。更详细可以去这里看。
现在来讲Java要用到链表应该怎么写。ArrayList和LinkedList都实现了链表,两者的区别在于与 ArrayList 相比,LinkedList 的增加和删除的操作效率更高,而查找和修改的操作效率较低。
链表用LinkedList较多。
3.1 Java中链表的操作
LinkedList 类位于 java.util 包中,使用前需要引入它,语法格式如下:
// 引入 LinkedList 类 import java.util.LinkedList; LinkedList<E> list = new LinkedList<E>(); // 普通创建方法 或者 LinkedList<E> list = new LinkedList(Collection<? extends E> c); // 使用集合创建链表
创建一个简单的链表实例:
import java.util.LinkedList; public class RunoobTest { public static void main(String[] args) { LinkedList<String> sites = new LinkedList<String>(); sites.add("Google"); sites.add("Runoob"); sites.add("Taobao"); sites.add("Weibo"); System.out.println(sites); } }
以上实例,执行输出结果为:
[Google, Runoob, Taobao, Weibo]
其他操作可参考这个表格
方法 描述 addFirst() 在表头增加一个元素 addLast() 在表尾增加一个元素 removeFirst() 从表头移除一个元素 removeLast() 从表尾移除一个元素 getFirst() 获得表头的元素 getLast() 获得表尾的元素 3.2 Java实现链表
想看Java中链表是如何实现以及基本的操作可以看这个博客,讲的很清楚,我就不在这里贴代码了。java ListNode 链表
-
Java实现单链表的常用方法
2019-08-21 17:26:20单链表:即单向链表,只能通过一个方向去遍历链表,由数据域(data)和指针域(next)组成。节点与节点之间通过指针来连接,每个节点指向自身的下一个节点,头节点为head,它的前一个节点为空;尾节点的下一个节点为...单链表:即单向链表,只能通过一个方向去遍历链表,由数据域(data)和指针域(next)组成。节点与节点之间通过指针来连接,每个节点指向自身的下一个节点,头节点为head,它的前一个节点为空;尾节点的下一个节点为null;结构如下图:
创建节点类,设置数据域和指针域,添加get和set方法public class SingleLinkedNode { // 数据域 private int data; // 指针域 private SingleLinkedNode next; public SingleLinkedNode() { } public int getData() { return data; } public void setData(int data) { this.data = data; } public SingleLinkedNode getNext() { return next; } public void setNext(SingleLinkedNode next) { this.next = next; } }
创建链表head,实现链表的遍历,新增,删除,查找操作。
public class MyLinkedList { /** * 在指定位置添加节点 * * @param pointNode 指定位置之后插入节点 * @param newNode 即将插入的节点 */ public static void insert(SingleLinkedNode pointNode, SingleLinkedNode newNode) { SingleLinkedNode next = pointNode.getNext();// 记录插入节点pointNode的下一个结点 pointNode.setNext(newNode);//pointNode的next指向新结点 newNode.setNext(next);//把pointNode结点的next指向新节点的next结点 System.out.println("插入节点node6成功!"); } /** * 遍历 * * @param head 链表 */ public static void query(SingleLinkedNode head) { while (head != null) { System.out.print(head.getData() + " "); head = head.getNext(); } System.out.println(); } /** * 查找数据 * * @param head * @param data */ public static void findData(SingleLinkedNode head, int data) { while (head != null) { if (head.getData() == data) { System.out.println("成功找到data:" + data); return; } head = head.getNext(); } System.out.println("未找到data:" + data); } /** * 删除结点q * * @param head 链表 * @param q 删除的结点 */ public static void delete(SingleLinkedNode head, SingleLinkedNode q) { // q不为空,q的下一个结点也不为空 if (q != null && q.getNext() != null) { // 思路:把q与q的next交换,交换后直接指向q的next的next,q就被删除了 SingleLinkedNode p = q.getNext(); q.setData(p.getData()); q.setNext(p.getNext()); } // 删除最后一个节点 if(q.getNext() == null) { while (head != null) { // 遍历前面的链表,当该节点的next就是q的时候 // 然后把q设置成null if (head.getNext() != null && head.getNext() == q) { head.setNext(null); break; } head = head.getNext(); } } } public static void main(String[] args) { SingleLinkedNode node1 = new SingleLinkedNode(); node1.setData(0); SingleLinkedNode node2 = new SingleLinkedNode(); node2.setData(1); SingleLinkedNode node3 = new SingleLinkedNode(); node3.setData(2); SingleLinkedNode node4 = new SingleLinkedNode(); node4.setData(3); SingleLinkedNode node5 = new SingleLinkedNode(); node5.setData(4); node1.setNext(node2); node2.setNext(node3); node3.setNext(node4); node4.setNext(node5); node5.setNext(null); // 遍历链表 query(node1); // node3 之后插入链表node6 SingleLinkedNode node6 = new SingleLinkedNode(); node6.setData(6); insert(node3, node6); query(node1); // 在链表中查找数据4 findData(node1, 4); // 删除节点node3 delete(node1, node3); query(node1); } }
-
java实现链表
2019-09-24 08:44:02链表是一种物理存储单元上非连续、非顺序的存储结构。 java代码实现单链表,插入,删除和遍历等功能。 链表能够灵活的进行插入和删除操作,时间复杂度为O(1),链表的查找时间复杂度为O(n)。 -
JAVA单链表的简单操作(递增单链表插入数据,链表逆置,链表逆序合成)
2020-12-21 22:30:42JAVA写一个单链表 1、已知带头结点的动态单链表 L 中的结点是按整数值递增排序的,试写一 算法将值为 x 的结点插入到表 L 中,使 L 仍然有序。要求算法的时间复杂度为 O(n),空间复杂度为 O(1)。 2、设计一算法,... -
Java链表
2020-12-20 14:26:16链表一、链表1、什么是链表2、链表共分几类?1、单链表2、双向链表3、循环链表 一、链表 1、什么是链表 链表 [Linked List]:链表是由一组不必相连(不必相连:可以连续也可以不连续)的内 存结构(节点),按特定... -
Java实现链表中元素的获取、查询和修改方法详解
2020-08-19 12:41:20主要介绍了Java实现链表中元素的获取、查询和修改方法,结合实例形式详细分析了Java针对链表中元素的获取、查询和修改相关原理、实现方法及操作注意事项,需要的朋友可以参考下 -
JAVA链表
2020-09-05 10:41:04JAVA中一个基本的链表节点就是这样的 public class HeroNode {//用类来做节点,一个节点就做完了 public int age; public String name; public String nickName; public HeroNode next;//使用类做指针,指向下... -
Java链表(Linked List)基本原理与实现方法入门示例
2020-08-19 12:42:26主要介绍了Java链表(Linked List)基本原理与实现方法,结合实例形式分析了Java链表(Linked List)的功能、原理、实现方法与操作注意事项,需要的朋友可以参考下 -
Java链表中添加元素的原理与实现方法详解
2020-08-19 12:20:53主要介绍了Java链表中添加元素的原理与实现方法,结合实例形式详细分析了Java实现链表中添加元素的相关原理、操作技巧与注意事项,需要的朋友可以参考下 -
JAVA链表中的回文链表结构
2022-04-02 19:05:03作为一个java初学者,最近遇到了回文链表结构这个难题,经过一番学习总算搞清楚个大概。 先来说一下什么是回文链表,会问链表在我们生活中经常能够遇到。会问链表的结构就是 例如:1->2->3->2->1。... -
Java 单向链表、双向链表:结构定义与初始化方法
2022-03-01 23:18:49Java 链表初始化 -
Java LinkedList 双向链表实现原理
2021-01-20 02:48:03相信大家都明白 LinkedList 是基于双向链表而实现的,本篇文章主要讲解一下双向链表的实现,并且我们参考 LinkedList 自己实现一个单链表尝试一下。 什么是链表? 简单的来讲一下什么是链表:首先链表是一种线性的... -
Java模拟单链表和双端链表数据结构的实例讲解
2020-09-02 13:16:48主要介绍了Java模拟单链表和双端链表数据结构的实例,注意这里的双端链表不是双向链表,是在单链表的基础上保存有对最后一个链接点的引用,需要的朋友可以参考下 -
Java链表详解--通俗易懂(超详细,含源码)
2021-11-30 18:54:19概念 ...由于不必须按顺序存储,链表在插入的时候可以达到O(1)的复杂度,比另一种线性表顺序表快得多,但是查找一个节点或者访问特定编号的节点则需要O(n)的时间,而线性表和顺序表相应的时间复杂 -
Java链表——遍历、查找、求链表长度
2021-07-18 22:57:27在能够遍历链表的情况下做查找简直易如反掌。只需添加一个判断语句即可。(采用了返回 Boolean 结果的形式) public boolean Search(int val) { ListNode indexNode = head; while(indexNode != null) { if ... -
约瑟夫问题 java 链表方法
2011-12-11 14:58:42Josephu 问题为:设编号为1,2,… n的n个人围坐一圈,约定编号为k(1 )的人从1开始报数,数到m的那个人出列,它的下一位又从1开始报数,数到m的那个人又出列,依次类推,...运用了链表解决该问题 包名:com.yueshefu; -
java链表的各种操作
2021-02-12 21:31:13java里面没有指针的说法,所以初始化的时候,就是新建一个null节点就是一个空链表了。//C里面链表会有头指针,头指针指向头节点如果想向空链表插入第一个节点,直接head=newNode;注意的情况是如果想循环链表,一定... -
Java链表可直接赋值
2021-12-08 16:21:54@Test public void test(){ List<String> list1 = new ArrayList<>(); list1.add("A"); list1.add("B"); List<String> list2 = new ArrayList<>(); list2.add("C");... . -
链表的原理及java实现代码示例
2020-08-28 19:07:39主要介绍了链表的原理及java实现代码示例,涉及单向链表的基本介绍,单向链表的Java实现代码分享等相关内容,具有一定参考价值,需要的朋友可以参考下。 -
Java链表的常用算法原理
2022-03-13 12:35:37方法:快慢指针法 定义两个指针都指向head节点,fast指针每次移动两步,slow指针每次移动一步,当fast不能再往后走时,slow此时指向的是中间值 代码: //找到链表的中间值 public Node findMid() { //定义... -
Java链表中元素删除的实现方法详解【只删除一个元素情况】
2020-08-19 12:43:04主要介绍了Java链表中元素删除的实现方法,结合实例形式分析了java只删除链表中一个元素的相关操作原理、实现方法与注意事项,需要的朋友可以参考下 -
Java~链表反转/链表逆置的多种方法(超详细,含完整代码)
2021-11-03 12:13:431.先定义一个last用于表示反转后链表的第一个结点 2.然后遍历单链表,每访问一个结点就将这个结点进行头插,头插到最前面,说白了就是把单链表分成了两个部分,一个是以head为首,一个是以cur为... -
Java实现循环链表
2020-03-22 23:21:24用Java定义一个循环链表,实现链表的基本操作: 初始化*、获取头结点、添加新元素*、删除链表元素 、获取链表元素*、查找链表元素*、更新链表中某个元素、 判断链表是否为空、求链表元素个数、输出链表元素、清空... -
java实现单链表、双向链表
2020-09-02 14:21:17主要为大家详细介绍了java实现单链表、双向链表的相关资料,具有一定的参考价值,感兴趣的小伙伴们可以参考一下 -
java 链表数据结构
2021-03-14 11:31:34首先,单链表相对于队列的优势在于存储地址...下面直接进入正题:先要定义一个结点类,如下:Java代码public classNode {Node next;//下一个结点的引用Object obj;//结点元素publicNode(Object obj){this.obj=obj;... -
JAVA——链表
2022-04-21 09:03:35一、链表概念及结构 链表:链表是一种物理存储结构上非连续存储结构,数据元素的逻辑顺序是通过链表中的引用链接次序实现的。如下图:(通俗的说:就是由一个个节点组成,这些节点逻辑上连续,物理上不连续) ...