Java链表结构,java实现链表结构

　　00-1010知道链表的结构单向链表双向链表加深对链表结构的理解实现单向双向链表的反转删除链表中所有给定值。

认识链表结构

单链表在内存中的表示：

　　可以看到，链表的节点包含数据字段和对下一个节点的引用，链表的最后一个节点指向null(空白区域)。

　　我们可以根据这一定义，用Java语言表示一下单向链表的结构：

　　公共类节点{ public int value公共节点next公共节点(int value){ this . value=value；}}在链表的结构中，有数据字段值，有指向下一个节点的引用next。

　　提示：这里的值也可以定义为泛型。

单向链表

我们再来看一下双向链表的结构：

　　双向链表中的一个节点有一个数字字段，一个对它的前一个节点的引用和一个对它的后一个节点的引用，从中我们可以定义

　　双向链表的结构：

　　公共类DoubleNode { public int value公共DoubleNode prepublic DoubleNode nextpublic double node(int value){ this . value=value；}}

双向链表

加深对链表结构的理解

说明：

　　对于一个链表如图所示：

　　反转意味着反转原始链表上节点的指针。原来的指针是：a-b-c-d-null，变成了现在的指针：d-c-b-a-null。

　　即反转后的结构如图所示：

　　这个题目不难。让我们改变一下指针的方向。

　　设计这样一个函数，其过程是调整链表的每个节点的指针，那么这个函数的元素是：

　　它是返回值链表的新头节点，可以保证函数执行后，原来的链表变成一个有新头节点的链表，需要传入一个链表。使用头节点来表示解题技巧：定义了两个节点引用来帮助我们反转指针。

　　代码实现：

　　公共静态节点reverseNode(节点头){ Node pre=nullNode next=null//最后让head指向null while (head！=null){ next=head . next；head.next=prepre=头；head=next}返回pre}我们来模拟一下这个函数的执行过程。

　　链表原始状态：

　　方法开始执行，此时head.next不为空，因此，执行以下步骤：

　　Next=head.Next:让next指向head的下一个节点(当前节点)，即b。

　　Head.next=pre:让当前节点的下一个节点指向pre，即null

　　此时，当前节点指向B而不是null。

　　Pre=head:让Pre指向当前节点head=next:让当前节点指向next，相当于移动头节点，直到移动到原来的尾节点。

　　r">

　　第一次循环执行结束，此时head为b，不是null，所以继续循环，执行流程：

　　此时head为c，不是null，所以继续循环，执行流程如下：

　　同理，此时head为d，不是null，继续循环：

　　这是就完成了单链表的反转步骤。

　　有了单链表反转的经验，我们很容易就能实现双向链表的反转，代码如下：

public DoubleNode reverseDoubleNode(DoubleNode head) { DoubleNode pre = null; DoubleNode next = null; while (head != null) { next = head.next; //操作（移动）当前节点 head.next = pre; head.pre = next; pre = head; head = next; } return pre;}

实现把链表中给定的值都删除

题如：给定一个单链表头节点head，以及一个整数，要求把链表中值为给定整数的节点都删除。

　　实现思路：

　　要实现的函数需要给我传一个头节点以及给定的数值，头节点确定链表。func(Node head, int num)。函数给不给返回值，返回值是什么？试想，针对链表3 -> 5 -> 4 -> 3 -> 4 -> 5，假如要删除4，那么新链表就是3 -> 5-> 3 -> 5，头节点仍然是原来的节点3；而如果要删除值为3的节点呢，删除后就是5 -> 4 -> 4 -> 5，头节点变了。因此，我们要设计的这个函数需要返回新链表的头节点。上述分析得知，需要返回新链表的头节点，因此也就是要返回第一个不是给定值的节点（因为给定值的节点都要被删除掉）。

//head移动到第一个不需要删除的位置：边界条件while (head != null) { if (head.value != num) { break; } //head右移 head = head.next;}//跳出循环之后，head的情况：//1. head = null，这种情况是链表中的值全部是给定值，全删了//2. head != null// 中间操作//最终返回head：第一个不是给定值的节点return head;

head移动到第一个不需要删除的位置后，head若为null，表示所有节点都删除了，直接返回就可以了；若head不为null，借助两个辅助变量Node pre和cur，从head处开始往next走，遇到给定值就跳过。

Node pre = head;Node cur = head;while (cur != null) { if (cur.value == num) { pre.next = cur.next; } else { pre = cur; } cur = cur.next;}

这一执行过程图解如下：

　　通过上述分析，写出完整实现代码：

public static Node remove (Node head, int num) { while (head != null) { if (head.value != num) { break; } head = head.next; } Node pre = head; Node cur = head; while (cur != null) { if (cur.value == num) { pre.next = cur.next; } else { pre = cur; } cur = cur.next; } return head;}

小结

针对链表这种数据结构进行了一些简单的分析，通过两个例子熟悉了链表的结构。

　　针对链表的操作，需要注意的就是指针指向以及边界问题，后续关于链表的算法还会遇到。

　　到此这篇关于Java链表数据结构及其简单使用方法解析的文章就介绍到这了,更多相关Java链表数据结构内容请搜索盛行IT以前的文章或继续浏览下面的相关文章希望大家以后多多支持盛行IT！

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。