`
michael8335
  • 浏览: 187578 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

单链表

阅读更多
    Java中有两种表的数据结构:ArrayList和LinkedList,其中ArrayList以数组的形式保存数据,即相邻两个元素在物理位置和逻辑位置上都相邻,LinkedList是采用链表的形式保存数据,即逻辑相邻的元素,物理位置不一定相邻,链表分为单链表、双向链表等,其中单链表是最简单的链表,下面就简单介绍一下单链表
    单链表中每个元素被称为“连接点”,连接点不仅保存了本身的数据对象,还保存的对下一个连接点的引用,这样才能使物理上不相邻的元素在逻辑上相邻。
链表结构入下图所示:

下面用Java代码实现一个简单的单链表
连接点类:
package com.yf.linkedlist;

public class Link {
	/*
	 * 下一个连接点的引用
	 */
	Link next;
	/*
	 * 需要保存的数据
	 */
	int iData;

	public Link(int iData) {
		this.iData = iData;
	}
	/*
	 * 用户打印每个连接点的值
	 */
	public void display(){
		System.out.print("["+iData+"]");
	}
}

链表类
package com.yf.linkedlist;

public class LinkList {
	// 对第一个链结点的引用
	Link first;

	/**
	 * 链表的构造方法
	 */
	public LinkList() {
		first = null;
	}

	/**
	 * 链表首部插入一个元素
	 * 
	 * @param iData
	 */
	public void insertFirst(int iData) {
		Link link = new Link(iData);
		link.next = first;
		first = link;
	}

	/**
	 * 删除链表首部元素
	 * 
	 * @return
	 */
	public Link deleteFirst() {
		Link temp = first;
		first = first.next;
		return temp;
	}

	/**
	 * 显示某个链表的所有元素
	 */
	public void display() {
		Link current = first;
		while (!(current == null)) {
			current.display();
			current = current.next;
		}
		System.out.println();
	}

	/**
	 * 查找链表中某个特定的元素
	 * 
	 * @param key
	 * @return
	 */
	public Link find(int key) {
		Link current = first;
		while (current.iData != key) {
			if (current.next == null) {
				return null;
			}
			current = current.next;
		}
		return current;
	}

	/**
	 * 删除链表中某个特定的元素
	 * 
	 * @param key
	 * @return
	 */
	public Link delete(int key) {
		Link current = first;
		Link previous = first;
		while (current.iData != key) {
			if (current.next == null) {
				return null;
			} else {
				previous = current;
				current = current.next;
			}
		}
		if (current == first) {
			first = first.next;
		} else {
			previous.next = current.next;
		}
		return current;
	}

	/*
	 * 计算链表的长度
	 */
	public int size() {
		int length = 0;
		Link current=first;
		if(current==null)
			return 0;
		while(current.next!=null){
			++length;
			current=current.next;
		}
		/*
		 * 由于While里面判断的是下一个链接点,所以总个数需加上本身的那一个
		 */
		return length+1;
	}
}

测试类:
package com.yf.linkedlist;

public class Main {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		LinkList linkList = new LinkList();
		System.out.println(linkList.size());
		for (int i = 1; i <= 10; i++) {
			linkList.insertFirst(i);
		}
		
		linkList.display();
		System.out.println(linkList.size());
		linkList.deleteFirst();
		System.out.println(linkList.size());
		linkList.display();
		linkList.delete(5);
		linkList.display();
	}

}


输出结果如下:

0
[10][9][8][7][6][5][4][3][2][1]
10
9
[9][8][7][6][5][4][3][2][1]
[9][8][7][6][4][3][2][1]
这里有一点需要说明,该链表类删除元素时,我们之需要是该元素失去引用即可,Java垃圾回收机制会自动回收该连接点所占用的内存
0
2
分享到:
评论

相关推荐

    使用C++实现单链表的基本操作:1、创建单链表2、遍历单链表3、单链表插入4、删除单链表5、判断是否为空6、单链表的

    本文将详细阐述如何使用C++来实现单链表的基本操作,包括创建、遍历、插入、删除、判断空、计算长度以及查找节点。 首先,我们从创建单链表开始。单链表是由一系列节点组成的数据结构,每个节点包含一个数据元素和...

    数据结构实验——单链表

    实验二 单链表实验 一、实验目的 1、掌握用Visual C++6.0上机调试单链表的基本方法 2、掌握单链表的插入、删除、查找、求表长以及有序单链表的合并算法的实现 二、实现内容 1、单链表基本操作的实现 在带头结点的...

    单链表 单链表 单链表 链表

    单链表是一种基础的数据结构,它在计算机科学中扮演着重要的角色,特别是在处理动态数据集合时。单链表由一系列节点组成,每个节点包含两部分:数据域和指针域。数据域存储实际的元素值,而指针域则指向链表中的下一...

    单链表的各种基本运算

    建立一个单链表,实现单链表的初始化,插入、删除节点等功能,以及确定某一元素在单链表中的位置。 (1) 初始化单链表; (2) 依次采用尾插入法插入a,b,c,d,e元素; (3) 输出单链表L; (4) 输出单链表L的长度...

    C++单链表实现大数加法

    C++单链表实现大数加法 大数加法是一种常见的算法问题,特别是在C++中实现大数加法时需要考虑到数字的位数和溢出问题。使用单链表来实现大数加法可以解决这个问题。本文将详细介绍如何使用C++单链表实现大数加法。 ...

    实验报告2 单链表的操作

    ### 实验报告2 单链表的操作 #### 一、实验背景与目标 本实验的主要目的是让学生通过实际操作,理解并掌握单链表这一基本的数据结构。单链表是一种线性表,其中每个元素都是一个节点,每个节点包含两部分:存储...

    单链表的基本操作验证

    ### 数据结构实验:单链表的基本操作验证 #### 引言 计算机技术的核心之一在于如何高效地表示和处理信息,这一过程涉及数据的组织、存储和运算方式。数据结构与算法构成了程序设计的基石,正如N.Wirth教授所提出...

    单链表的创建和插入

    ### 单链表的创建与插入 #### 一、单链表基础知识 单链表是一种基本的数据结构,其中每个元素包含两部分:数据域和指针域。数据域用于存储实际的数据,而指针域则指向下一个元素。单链表的特点在于它的线性顺序...

    数据结构单链表插入、删除和修改实验报告

    数据结构单链表插入、删除和修改实验报告 一、实验目的 1.理解数据结构中带头结点单链表的定义和逻辑图表示方法。 2.掌握单链表中结点结构的JAVA描述。 3.熟练掌握单链表的插入、删除和查询算法的设计与JAVA实现...

    单链表的基本操作

    1、从键盘上依次输入21、18、30、75、42、56,逆序创建单链表,并输出单链表中的各元素值。 2、分别在单链表的第3个位置和第9个位置插入67和10,给出插入成功或失败的信息,并输出单链表中的各元素值。 3、删除...

    单链表的创建、插入、删除

    ### 单链表的创建、插入、删除 #### 概述 本文将详细介绍单链表的基本操作:创建、插入和删除。单链表是一种常见的线性数据结构,它由一系列节点组成,每个节点包含两部分:存储数据的数据域和指向下一个节点的指针...

    基本的单链表的线性操作

    单链表是计算机科学中数据结构的基础,它是一种线性数据结构,由一系列节点(也称为元素或项)组成,每个节点包含数据以及一个指向下一个节点的引用(或称为指针)。在单链表中,数据的存储并不连续,而是通过指针...

    单链表的基本操作及实现

    单链表是一种基础的数据结构,它在计算机科学中扮演着重要的角色,特别是在数据存储和算法设计方面。单链表由一系列节点组成,每个节点包含数据元素以及指向下一个节点的引用,最后一个节点的引用通常为null,标志着...

    线性单链表的演示详细操作

    线性单链表是计算机科学中一种基本的数据结构,它在程序设计中有着广泛的应用。本文将详细探讨线性单链表的概念、操作以及其实现方法。 线性单链表是一种顺序存储结构,由一系列相同类型的数据元素构成,每个元素...

    单链表-实验报告.doc

    在计算机科学与技术领域,单链表是一种重要的基础数据结构,它由一系列节点组成,每个节点包含数据域和指针域,其中指针域指向下一个节点。单链表的节点之间通过指针连接,形成一条单向的线性结构。单链表的特点是...

    有序的单链表中插入和删除

    ### 有序单链表中的插入与删除操作 在数据结构的学习过程中,单链表是一种非常基础且重要的线性数据结构。对于单链表的操作主要包括创建、遍历、插入、删除等,而当单链表中的元素是按照一定的顺序排列时(如本例中...

    Java实现单链表以及单链表的操作.zip

    单链表是一种简单但灵活的数据结构,常用于实现各种抽象数据类型,如队列、栈和映射。本教程将深入探讨如何使用Java语言来实现单链表及其相关操作。 首先,我们来理解单链表的基本概念。单链表由一系列节点组成,每...

Global site tag (gtag.js) - Google Analytics