`
didixp
  • 浏览: 13262 次
  • 性别: Icon_minigender_1
  • 来自: 沈阳
最近访客 更多访客>>
社区版块
存档分类
最新评论

Java数据结构和算法--链表

阅读更多
http://yongsky.iteye.com/blog/128951
(1)简单链表
package ChapterFive;

class Link<E> {

	public E data;

	public Link<E> next;

	public Link(E data) {
		this.data = data;
	}
}

class LinkList<E> {

	public Link<E> first;
	//链表中数据项的个数
	public int size;

	public LinkList() {
		first = null;
		size = 0;
	}
	//在表头插入新的数据
	public void insertFirst(E value) {
		Link<E> link = new Link<E>(value);
		link.next = first;
		first = link;
		size++;
	}
	//判断链表是否为空
	public boolean isEmpty() {
		return size == 0;
	}
	//删除表头
	public Link<E> deleteFirst() {
		Link<E> temp = first;
		first = first.next;
		size--;
		return temp;
	}
	//输出链表中的所有数据
	public void display() {
		Link<E> curr = first;
		while (curr != null) {
			System.out.print(curr.data + " ");
			curr = curr.next;
		}
		System.out.println();
	}
	//返回链表中数据项的个数
	public int size() {
		return size;
	}
	//获取从头至尾的第i个数据项
	public Link<E> get(int i) {
		if (i > size() - 1 || i < 0)
			try {
				throw new IndexOutOfBoundsException();
			} catch (Exception e) {
				e.printStackTrace();
			}
		Link<E> curr = first;
		for (int n = 0; n < size(); n++) {
			if (n == i)
				return curr;
			else
				curr = curr.next;
		}
		return null;
	}
	//输出从头至尾的第i个数据项
	public void remove(int i) {
		if (i == 0)
			deleteFirst();
		else if (i == size() - 1)
			get(i - 1).next = null;
		else {
			get(i - 1).next = get(i + 1);
		}
		size--;
	}
}

public class Link_list {
	public static void main(String[] args) {
		LinkList<Long> ll = new LinkList<Long>();
		for (int i = 0; i < 10; i++) {
			Long value = (long) (Math.random() * 100);
			ll.insertFirst(value);
		}
		ll.display();
		while (!ll.isEmpty()) {
			ll.deleteFirst();
			ll.display();
		}
		System.out.println("Ok");
	}
}

(2)链栈
package ChapterFive;

class LinkStack<E> {

	LinkList<E> linkList;

	int size;

	public LinkStack() {
		size = 0;
		linkList = new LinkList<E>();
	}
	//入栈
	public void push(E value) {
		linkList.insertFirst(value);
		size++;
	}
	//出栈
	public Link<E> pop() {
		size--;
		return linkList.deleteFirst();
	}
	//返回栈顶元素
	public Link<E> top() {
		return linkList.first;
	}
	//判断栈是否为空
	public boolean isEmpty() {
		return size == 0;
	}
	//显示栈中的全部数据
	public void display() {
		linkList.display();
	}
}

public class Link_stack {
	public static void main(String[] args) {
		LinkStack<Long> ls = new LinkStack<Long>();
		for (int i = 0; i < 10; i++) {
			Long value = new Long((long) (Math.random() * 100));
			ls.push(value);
		}
		while (!ls.isEmpty()) {
			ls.pop();
			ls.display();
		}
		System.out.println("Ok");
	}
}

(3)有序表
package ChapterFive;

class SortedLink {

	public Link<Long> first;

	int size;

	public SortedLink() {
		first = null;
		size = 0;
	}
	//向有序链表中插入数据
	public void insert(long value) {
		Link<Long> newLink = new Link<Long>(value);
		Link<Long> previous = null;
		Link<Long> curr = first;
		while (curr != null && (value > curr.data)) {
			previous = curr;
			curr = curr.next;
		}
		if (previous == null)// 链表为空(在表头插入)
			first = newLink;
		else
			previous.next = newLink;//插入新的节点
		newLink.next = curr;
		size++;
	}
	//删除第一个节点
	public Link<Long> remove() {
		Link<Long> temp = first;
		first = first.next;
		size--;
		return temp;
	}
	//判断链表是否为空
	public boolean isEmpty() {
		return size == 0;
	}
	//输出链表的所有数据
	public void display() {
		Link<Long> curr = first;
		while (curr != null) {
			System.out.print(curr.data + " ");
			curr = curr.next;
		}
		System.out.println();
	}
}

public class SortedLinkApp {
	public static void main(String[] args) {
		SortedLink sl = new SortedLink();
		for (int i = 0; i < 10; i++) {
			sl.insert((long) (Math.random() * 100));
		}
		while (!sl.isEmpty()) {
			sl.remove();
			sl.display();
		}
	}
}

(4)双向链表
package ChapterFive;

class DoubleLink<E> {

	public Link<E> first;

	public Link<E> last;

	int size;

	@SuppressWarnings("hiding")
	class Link<E> {
		public E data;

		public Link<E> next;// 链表的下一项

		public Link<E> previous;// 链表的前一项

		public Link(E value) {
			this.data = value;
		}
	}

	public DoubleLink() {
		first = null;
		last = null;
		size = 0;
	}

	// 在链表的首部插入一项
	public void insertFirst(E value) {
		Link<E> newLink = new Link<E>(value);
		if (isEmpty())// 如果链表为空则first == last
			last = newLink;
		else
			first.previous = newLink;// 确定原first与newLink的前后关系
		newLink.next = first;
		first = newLink;// 设置新的first值
		size++;
	}

	// 在链表的尾部插入一项
	public void insertLast(E value) {
		Link<E> newLink = new Link<E>(value);
		if (isEmpty())// 如果链表为空则last == first
			first = newLink;
		else {
			last.next = newLink;// 确定原last与newLink的前后关系
			newLink.previous = last;
		}
		last = newLink;// 设置新的last值
		size++;
	}

	// 删除双向链表的表头
	public Link<E> deleteFirst() {
		Link<E> temp = first;
		if (first.next == null)// 链表中只有一项数据
			last = null;
		else
			first.next.previous = null;// 销毁原链表的头部
		first = first.next;
		size--;
		return temp;
	}

	// 删除链表的最后一项
	public Link<E> deleteLast() {
		Link<E> temp = last;
		if (first.next == null)// 链表中只有一项数据
			first = null;
		else
			last.previous.next = null;// 销毁原链表的尾部
		last = last.previous;
		size--;
		return temp;
	}

	// 判断链表是否为空
	public boolean isEmpty() {
		return size == 0;
	}

	// 输出链表中的所有数据项
	public void display() {
		Link<E> curr = first;
		while (curr != null) {
			System.out.print(curr.data + " ");
			curr = curr.next;
		}
		System.out.println();
	}
}

public class DoubleLinkApp {
	public static void main(String[] args) {
		DoubleLink<Integer> dl = new DoubleLink<Integer>();
		for (int i = 0; i < 5; i++) {
			dl.insertFirst((int) (Math.random() * 100));
		}
		for (int i = 0; i < 5; i++) {
			dl.insertLast((int) (Math.random() * 100));
		}
		dl.display();
		while (!dl.isEmpty()) {
			dl.deleteFirst();
			dl.deleteLast();
			dl.display();
		}
		System.out.println("Ok");
	}
}
分享到:
评论

相关推荐

    Java数据结构和算法-带书签目录扫描版

    《Java数据结构和算法-带书签目录扫描版》是一本深入探讨Java编程语言中数据结构和算法的书籍。此扫描版特别包含了完整的书签目录,使得读者在电子版阅读时能够快速定位到所需章节,提高了学习和查阅的效率。 在...

    Java数据结构和算法-第二版-高清扫描版-带目录书签

    《Java数据结构和算法》第二版是一本深入探讨Java编程中数据结构与算法的权威书籍。这本书涵盖了在软件开发中至关重要的基础知识,旨在帮助程序员提升解决问题的能力和代码效率。高清扫描版提供了清晰的文本和图表,...

    JAVA数据结构与算法-第二版

    美国计算机科学家Robert Lafore的著作《JAVA数据结构与算法-第二版》,经由计晓云、赵研等人的翻译,成为深入探讨这些概念的卓越教材。本书不仅涵盖了基础理论,还提供了大量Java语言中的实现示例,使得读者能够直观...

    java数据结构与算法.pdf

    Java作为广泛应用的编程语言,其在实现数据结构和算法时有着丰富的库支持和优秀的可读性。下面将对标题和描述中提到的一些关键知识点进行详细解释。 1. **数据结构**: - **稀疏数组**:当大量数据中大部分为零或...

    数据结构与算法--Java语言描述

    数据结构与算法是计算机科学的基础,对于任何编程语言来说,理解和掌握它们都是至关重要的,特别是对于Java语言。在这个“数据结构与算法--Java语言描述”的资料中,我们有望深入理解这些核心概念,并通过Java语言来...

    Java数据结构和算法-学习笔记

    本文基于《Java数据结构与算法》的学习笔记,旨在帮助读者更好地理解和掌握这些核心概念。 #### 二、数据结构概述 数据结构是指一组数据的集合以及它们之间的关系,以及在这组数据上定义的操作。常见的数据结构包括...

    数据结构与算法-java

    数据结构与算法是计算机科学的基础,对于理解和设计高效的软件至关重要。在Java编程中,理解这些概念可以帮助开发者编写出性能优异的程序。以下是基于标题“数据结构与算法-java”及描述中提到的“数据结构与算法...

    Java数据结构和算法中文第二版

    根据提供的信息,“Java数据结构和算法中文第二版”这本书主要关注的是数据结构与算法的相关内容。下面将基于这些信息,详细介绍数据结构与算法的核心概念、重要性和应用领域,以及在Java编程环境中如何实现这些概念...

    Java数据结构和算法.pdf

    资源摘要信息是关于Java数据结构和算法的知识点总结,涵盖了数组、栈与队列、链表、递归、哈希表、高级排序、二叉树、红黑树、堆、带权图等数据结构和算法概念。 一、数组 * 数组是相同类型变量的集合,可以使用...

    Java数据结构和算法中文第二版_Java数据结构_

    《Java数据结构和算法中文第二版》是一本深入探讨Java编程中数据结构和算法的书籍。数据结构是计算机科学的基础,它涉及到如何有效地组织和存储数据,以便在各种操作下高效地访问和修改。算法则是解决问题的具体步骤...

    Java数据结构和算法(第二版)+源代码+Applets

    Java数据结构和算法是计算机科学中的核心概念,对于任何Java开发者来说,理解和掌握它们都是至关重要的。本资源包“Java数据结构和算法(第二版)+源代码+Applets”为学习者提供了一个全面且深入的学习平台,涵盖了...

    Java数据结构和算法(第二版).zip

    《Java数据结构和算法》(第2版)介绍了计算机编程中使用的数据结构和算法,对于在计算机应用中如何操作和管理数据以取得最优性能提供了深入浅出的讲解。全书共分为15章,分别讲述了基本概念、数组、简单排序、堆和...

    C、C++、JAVA数据结构与算法电子书

    C、C++和Java都是广泛使用的编程语言,它们在处理数据结构和算法时各有特点。以下是对这三种语言在数据结构与算法方面的一些关键知识点的详细阐述: 1. **数据结构**: - **数组**:基本的数据结构,用于存储同...

    hello-algo-数据结构与算法-zh-csharp.pdf

    本书《Hello 算法》是为了帮助读者学习数据结构与算法而编写的,作者靳宇栋(Krahets)认为刷题虽然是学习算法的一种方法,但对于基础不足的同学来说,可能会感到困扰和挫折。因此,本书旨在引导读者探索数据结构与...

    java数据结构和算法学习笔记

    ### Java数据结构与算法学习笔记知识点总结 #### 一、数据结构概述 数据结构是对数据的一种组织形式,它决定了数据的存储方式以及处理数据的方法。常见的数据结构包括但不限于数组、链表、栈、队列、二叉树、图等...

    Java数据结构和算法(第二版)+随书源代码+applet小程序

    《Java数据结构和算法(第二版)》是一本专为希望深入理解Java编程中的数据结构与算法的读者设计的书籍。这本书的特点是从基础知识逐步引导读者进入复杂领域,通过结合实际的Applet小程序,使得理论知识变得生动直观。...

    Java数据结构与算法-笔记-代码-课件-资料

    内容包括: 稀疏数组、单向队列、环形队列、单向链表、双向链表、环形链表、约瑟夫问题、栈、前缀、中缀、后缀表达式、中缀表达式转换为后缀表达式、递归与回溯、迷宫问题、八皇后问题、算法的时间复杂度、冒泡排序、...

    java数据结构和算法

    java 数据结构和算法, 排序算法, 数组,链表,二叉树

Global site tag (gtag.js) - Google Analytics