java链表,java链表遍历

本文目录一览：

• 1、java怎么用链表实现
• 2、. java怎么创建链表
• 3、在Java中如何实现双向链表?
• 4、java基本链表
• 5、用java如何创建一个单链表和双链表

java怎么用链表实现

在数据结构中经常看见的一个基本概念-链表。

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

在Java中，对于链表的实现都是基于引用数据类型操作的。实现大致如下：

定义节点类Node，节点的概念很重要，一个链表是由各各节点连接在一起组成的。在节点类Node中定义节点内容及指向下一节点的引用，再增加一个添加节点的方法即可完成链表实现。

链表有很多种不同的类型：单向链表，双向链表以及循环链表。在执行效率上，相比数组而言，链表插入快查找慢，开发中得根据实际业务使用。

. java怎么创建链表

java中创建链表的例子：

package zx;

class Link{

private Node root;

class Node{

private String name;

private Node Next;

public Node(String name){

this.name = name;

}

public String getName(){

return this.name;

}

public void addNode(Node newNode){

if(this.Next==null){

this.Next = newNode;

}else{

this.Next.addNode(newNode);

}

}

public void printNode(){

System.out.print(this.name + “–“);

if(this.Next!=null){

this.Next.printNode();

}

}

};

public void add(String name){

Node newNode = new Node(name);

if(this.root==null){

this.root = newNode;

}else{

this.root.addNode(newNode);

}

}

public void print(){

if(this.root!=null){

this.root.printNode();

}

}

};

public class LinkDemo {

/**

* @param args

*/

public static void main(String[] args) {

// TODO Auto-generated method stub

Link link = new Link();

link.add(“根节点”);

link.add(“第一节点”);

link.add(“第二节点”);

link.add(“第三节点”);

link.add(“第四节点”);

link.print();

System.out.println(“null”);

}

}

在Java中如何实现双向链表?

双向链表：就是有双向指针，即双向的链域。\x0d\x0a链结点的结构：\x0d\x0a┌────┬────┬────────┐\x0d\x0a│ data │ next │ previous │\x0d\x0a└────┴────┴────────┘\x0d\x0a双向链表不必是双端链表(持有对最后一个链结点的引用)，双端链表插入时是双向的。\x0d\x0a有两条链：一条从头到尾，一条从尾到头，删除遍历时也是双向的。\x0d\x0a/**\x0d\x0a * 双向链表\x0d\x0a */\x0d\x0apublic class DoublyLinkedList {\x0d\x0a private Link head; //首结点\x0d\x0a private Link rear; //尾部指针\x0d\x0a public DoublyLinkedList() { }\x0d\x0a public T peekHead() {\x0d\x0a if (head != null) {\x0d\x0a return head.data;\x0d\x0a }\x0d\x0a return null;\x0d\x0a }\x0d\x0a public boolean isEmpty() {\x0d\x0a return head == null;\x0d\x0a }\x0d\x0a public void insertFirst(T data) {// 插入 到 链头\x0d\x0a Link newLink = new Link(data);\x0d\x0a if (isEmpty()) {//为空时，第1次插入的新结点为尾结点\x0d\x0a rear = newLink;\x0d\x0a } else {\x0d\x0a head.previous = newLink; //旧头结点的上结点等于新结点\x0d\x0a }\x0d\x0a newLink.next = head; //新结点的下结点旧头结点\x0d\x0a head = newLink; //赋值后，头结点的下结点是旧头结点，上结点null\x0d\x0a }\x0d\x0a public void insertLast(T data) {//在链尾 插入\x0d\x0a Link newLink = new Link(data);\x0d\x0a if (isEmpty()) {\x0d\x0a head = newLink;\x0d\x0a } else {\x0d\x0a rear.next = newLink;\x0d\x0a }\x0d\x0a newLink.previous = rear;\x0d\x0a rear = newLink; //赋值后，尾结点的上结点是旧尾结点，下结点null\x0d\x0a }\x0d\x0a public T deleteHead() {//删除 链头\x0d\x0a if (isEmpty()) return null;\x0d\x0a Link temp = head;\x0d\x0a head = head.next; //变更首结点，为下一结点\x0d\x0a if (head != null) {\x0d\x0a head.previous = null;\x0d\x0a } else {\x0d\x0a rear = null;\x0d\x0a }\x0d\x0a return temp.data;\x0d\x0a }\x0d\x0a public T deleteRear() {//删除 链尾\x0d\x0a if (isEmpty()) return null;\x0d\x0a Link temp = rear;\x0d\x0a rear = rear.previous; //变更尾结点，为上一结点\x0d\x0a if (rear != null) {\x0d\x0a rear.next = null;\x0d\x0a } else {\x0d\x0a head = null;\x0d\x0a }\x0d\x0a return temp.data;\x0d\x0a }\x0d\x0a public T find(T t) {//从头到尾find\x0d\x0a if (isEmpty()) {\x0d\x0a return null;\x0d\x0a }\x0d\x0a Link find = head;\x0d\x0a while (find != null) {\x0d\x0a if (!find.data.equals(t)) {\x0d\x0a find = find.next;\x0d\x0a } else {\x0d\x0a break;\x0d\x0a }\x0d\x0a }\x0d\x0a if (find == null) {\x0d\x0a return null;\x0d\x0a }\x0d\x0a return find.data;\x0d\x0a }\x0d\x0a public T delete(T t) {\x0d\x0a if (isEmpty()) {\x0d\x0a return null;\x0d\x0a }\x0d\x0a Link current = head;\x0d\x0a while (!current.data.equals(t)) {\x0d\x0a current = current.next;\x0d\x0a if (current == null) {\x0d\x0a return null;\x0d\x0a }\x0d\x0a }\x0d\x0a if (current == head) {\x0d\x0a head = head.next;\x0d\x0a if (head != null) {\x0d\x0a head.previous = null;\x0d\x0a }\x0d\x0a } else if (current == rear) {\x0d\x0a rear = rear.previous;\x0d\x0a if (rear != null) {\x0d\x0a rear.next = null;\x0d\x0a }\x0d\x0a } else {\x0d\x0a //中间的非两端的结点，要移除current\x0d\x0a current.next.previous = current.previous;\x0d\x0a current.previous.next = current.next;\x0d\x0a }\x0d\x0a return current.data;\x0d\x0a }\x0d\x0a public boolean insertAfter(T key, T data) {//插入在key之后, key不存在return false\x0d\x0a if (isEmpty()) {\x0d\x0a return false;\x0d\x0a }\x0d\x0a Link current = head;\x0d\x0a while (!current.data.equals(key)) {\x0d\x0a current = current.next;\x0d\x0a if (current == null) {\x0d\x0a return false;\x0d\x0a }\x0d\x0a }\x0d\x0a Link newLink = new Link(data);\x0d\x0a if (current == rear) {\x0d\x0a rear = newLink;\x0d\x0a } else {\x0d\x0a newLink.next = current.next;\x0d\x0a current.next.previous = newLink;\x0d\x0a }\x0d\x0a current.next = newLink;\x0d\x0a newLink.previous = current;\x0d\x0a return true;\x0d\x0a }\x0d\x0a public void displayList4Head() {//从头开始遍历\x0d\x0a System.out.println(“List (first–last):”);\x0d\x0a Link current = head;\x0d\x0a while (current != null) {\x0d\x0a current.displayLink();\x0d\x0a current = current.next;\x0d\x0a }\x0d\x0a }\x0d\x0a public void displayList4Rear() {//从尾开始遍历\x0d\x0a System.out.println(“List (last–first):”);\x0d\x0a Link current = rear;\x0d\x0a while (current != null) {\x0d\x0a current.displayLink();\x0d\x0a current = current.previous;\x0d\x0a }\x0d\x0a }\x0d\x0a\x0d\x0a class Link {//链结点\x0d\x0a T data; //数据域\x0d\x0a Link next; //后继指针，结点 链域\x0d\x0a Link previous; //前驱指针，结点 链域\x0d\x0a Link(T data) {\x0d\x0a this.data = data;\x0d\x0a }\x0d\x0a void displayLink() {\x0d\x0a System.out.println(“the data is ” + data.toString());\x0d\x0a }\x0d\x0a }\x0d\x0a public static void main(String[] args) {\x0d\x0a DoublyLinkedList list = new DoublyLinkedList();\x0d\x0a list.insertLast(1);\x0d\x0a list.insertFirst(2);\x0d\x0a list.insertLast(3);\x0d\x0a list.insertFirst(4);\x0d\x0a list.insertLast(5);\x0d\x0a list.displayList4Head();\x0d\x0a Integer deleteHead = list.deleteHead();\x0d\x0a System.out.println(“deleteHead:” + deleteHead);\x0d\x0a list.displayList4Head();\x0d\x0a Integer deleteRear = list.deleteRear();\x0d\x0a System.out.println(“deleteRear:” + deleteRear);\x0d\x0a list.displayList4Rear();\x0d\x0a System.out.println(“find:” + list.find(6));\x0d\x0a System.out.println(“find:” + list.find(3));\x0d\x0a System.out.println(“delete find:” + list.delete(6));\x0d\x0a System.out.println(“delete find:” + list.delete(1));\x0d\x0a list.displayList4Head();\x0d\x0a System.out.println(“—-在指定key后插入—-“);\x0d\x0a list.insertAfter(2, 8);\x0d\x0a list.insertAfter(2, 9);\x0d\x0a list.insertAfter(9, 10);\x0d\x0a list.displayList4Head();\x0d\x0a }\x0d\x0a}

java基本链表

传进去的是new Node(“车厢A”)的引用

获取当前节点的下一个节点， Node(“车头！”) 的下一个节点是Node(“车厢A”)，Node(“车厢A”)的下一个节点是Node(“车厢B”)

用java如何创建一个单链表和双链表

单向链表

单向链表就是通过每个结点的指针指向下一个结点从而链接起来的结构。

单向链表的初始化：这里我所讲的链表都是头结点不参与计算的，也就是说第一个结点都是头结点后面的第一个结点。所以我要先申明一点，这里我把链表的初始化放在了构造函数部分，然后析构函数负责释放头结点的内存。

单向链表的创建过程：链表的创建就是添加结点到链表的最后，开始是添加一个结点到head结点后面，然后添加一个结点到上次添加的结点后面，每次新建的结点的指针总是指向NULL指针。从上面的示意图可以看出，我们需要一个辅助指针一直指向最后一个结点，这个辅助结点就是为了让每次添加的结点都放置在最后一个位置。

单向链表插入结点过程：源代码中的的插入结点函数我设置了一个指定位置，就是在指定位置插入结点。首先，通过位置变量position让ptemp结点移动到要插入位置的前一个位置，然后接下来的过程就是和创建链表的过程是一样的，把新建的结点添加到ptemp的后面。这里变量position可以从1到链表长度加1，意思就是如果不算头结点的话有3个结点，那你的position变量就可以从1到4，这是因为ptemp指针可以到第3个结点的位置，所以新建结点的位置就可以到4了。

单向链表删除结点过程：源代码中的删除结点函数也有一个指定位置变量，为了删除指定位置的结点。和插入结点一样通过变量position把ptemp移动到要删除结点的前一个位置，然后让ptemp结点中的指针指向要删除结点后面的一个结点，也就是ptemp结点的下一个的下一个结点，虽然这个结点可能为空，但是程序还是正常运行。但是这里和插入结点不同的是变量position只能从1到链表的长度，是因为ptemp移动到最后一个结点的时候，它的下一个结点为空，所以不不需要参与删除了。

双向链表

1.听名字可能就能猜到双向链表就是链表结点包含两个指针，一个指针是指向下一个结点的，另一个指针当然就是指向上一个结点的。

2.双向链表的初始化：由于这里的链表头结点不参与计算，所以头结点的pPre指针是一直指向NULL指针的。

3.双向链表的创建过程：由于双向链表的每个结点包含两个指针那么这个时候我们就要小心处理好每一个指针的指向，要不然会有很多意想不到的错误。同样的，和单向链表的创建过程一样，需要一个辅助指针来指向最后一个结点，然后每新建一个结点，这个结点的pNext指针都是指向NULL指针的，pPre指针指向上一个结点（这是和单向链表不同的地方），然后让上一个指针的pNext指向新建的结点，这样整个链表就连接起来了。

4.双向链表插入结点过程：知道了双向链表的创建过程，那么插入结点的过程就大同小异 了，有一点需要特别注意的就是这里的变量position范围也是从1到链表长度加1，但是如果待插入的位置是最后一个位置的话，情况就不同了，看到下面的图我们可以很好的理解，因为没新建一个结点的时候都需要处理两个指针，而且新建结点的下一个结点的pPre指针就需要指向这个新建的结点，但是有可能这个新建的结点可能就已经是最后一个结点了，那么这个时候再执行

ptemp-pNext-pPre = pnew;

这条指令的时候就会报错了，因为ptemp-pNext已经是个NULL指针了，那空指针哪里还有pPre呢。因此在程序中要进行一次判断，看看结点是否是最后一个结点。

5.双向链表删除结点的过程：要注意的问题和插入结点一样，看看这个结点是否为NULL。这里就不重复了。