数据结构--链表(java语言描述)

数据结构--链表(java语言描述)

文章目录

• 链表
• • 链表是什么
  • 链表的分类(单、双、循环)
  • 链表的基本 *** 作(java语言描述)

链表 链表是什么

链表是由一组不必相连的内存结构（结点） ，按特定的顺序链接在一起的抽象数据类型。它是最简单的动态数据结构。

在链表中，每个数据项都被包括在“节点”(Node)中，每个节点本身由两部分组成：

• 本身的信息，称为“数据域”；
• 指向直接后继的指针，称为“指针域”。
  节点是某个类的对象，这个类可以叫做Node。因为一个链表中有许多类似的节点，所以有必要用一个描述节点的类来表达节点。每个Node对象中都包含一个对下一个节点引用的字段（通常叫做next）。

定义节点类：

class Node
{
public Object Date; //定义一个Object类的数据域
public Node next;   //定义一个Node类的指针域
} 

链表的分类(单、双、循环)

链表常用的有三类： 单链表、双向链表、循环链表。
单链表：

双向链表：

循环链表：

链表的基本 *** 作(java语言描述)

首先定义一个节点类，及其基本的方法：（构造方法、找下一个节点、设置指针指向、找该节点的数据、判断是否有下一个节点）

public class Node {
	private String nodeName;//数据
	private Node next;//对下一个节点的引
	// 用数据域构造一个节点对象
	public Node(String nodeName) {
		this.nodeName = nodeName;
	}
	// 返回下一节点的对象
	public Node getNext() {
		return this.next;
	}
	// 设置本节点的链域
	public void setNext(Node next) {
		this.next = next;
	}
	// 返回节点的数据域
	public String getName() {
		return this.nodeName;
	}
	// 判断是否有下一节点
	public boolean hasNext() {
		boolean is = false;
		if (this.getNext() != null) {
			is = true;
		}
		return is;
	}
}

对链表的基本 *** 作有：
尾部追加节点：

public void addNode(String name) {
		Node p = head;  //定义指针p指向头节点
		Node node = new Node(name); //创建一个新节点name
		while (true) { 
			if (!p.hasNext()) { //p指向链表最后一个节点
				p.setNext(node); //设置p指向的下一个节点为新建的节点
				break;
			}
			p = p.getNext();  //迭代使p后移
		}
	}

插入节点：

//在inName后面插入一个节点nodeName
public boolean insertNode(String inName,String nodeName) {
		Node p = head;
		if (!p.hasNext()) { //如果头节点后面没有节点，即插入在头节点后面
			addNode(nodeName); //直接调用尾部追加方法
			return true;
		}
		while (p.hasNext()) { 
			if (p.getNext().getName().equals(inName)) { p指向插入节点的前驱
				Node node=new Node(nodeName);  //创建要添加的新节点
				node.setNext(p.getNext().getNext());//新节点的后继指向p的后继
				p.getNext().setNext(node); //p的后继节点指向新节点			
				break;
			}
			p = p.getNext(); //p指针后移
		}
		System.out.println("插入节点：" + nodeName);
		return true;
	}

删除节点

// nodeName为要删除节点的名称
public boolean delNode(String nodeName) {
		Node p = head; 
		if (!p.hasNext()) {   //p后面没有节点
			System.out.println("此表为空");
			return false;
		}
		while (p.hasNext()) {
			if (p.getNext().getName().equals(nodeName)) { //p的后继节点为nodeName
				p.setNext(p.getNext().getNext()); //设置p的后继为nodeName的后继
				break;
			}
			p = p.getNext(); //指针后移
		}

遍历链表

public void display() {
		Node p = head.getNext();
		while (p != null) {
			System.out.println(p.getName());
			p = p.getNext();
		}
	}

按内容查找

	public void contenFind(String name) {
		Node node = head;
		int i = 0;
		System.out.println("--------开始遍历--------");
		while (node != null) {
			if (node.getName().equals(name)) {
				System.out.println("被查找的节点为：" + node.getName());
				break;
			}
			i++;
			node = node.getNext();
		}
	}

按位置查找

public void orderFind(int num) {
		Node node = head;
		int i = 0;
		System.out.println("--------开始遍历--------");
		while (node != null) {
			if (i == num) {
				System.out.println("被查找的节点为：" + node.getName());
				break;
			}
			i++;
			node = node.getNext();
		}
	}