白天贴了一个链表的数据结构,基本上都是看着书写的,晚上自己动手写了一个,这里贴出来给大家砸鸡蛋哈,
1,链表节点
package pku.ss.datastructure.ILinkedList;
public interface ILinkedList {
/**
* get the size of the list
* @return the size of the list
*/
public int getSize();
/**
* Judge that if the list is empty
* @return true or false
*/
public boolean isEmpty();
/**
* make the list empty
*/
public void makeEmpty();
/**
* Judge that if the list contains the node whose element equals x
* @param x
* @return true or false
*/
public boolean contains(Object x);
/**
* remove the node whose element equals x, and return a
* boolean value that if there is a x in list then return true,
* else return false
* @param x
* @return true or false
*/
public boolean remove(Object x);
/**
* Insert a node behind k'st into list with node's element equals x
* @param x
* @param k
* @return true or false
*/
public boolean insert(Object x, int k);
/**
* get the first element of list
* @return element of the first node
*/
public Object getFirst();
/**
* get the last element of list
* @return element of the last node
*/
public Object getLast();
/**
* print the elements of the list
*/
public void printList();
}
2,链表结构
package pku.ss.datastructure.LinkedList;
import pku.ss.datastructure.ILinkedList.ILinkedList;
public class LinkedList implements ILinkedList {
private int size;
private ListNode header;
/**
* Initialize a list with max capability of 0
*
* @param size
*/
public LinkedList() {
this.size = 0;
header = new ListNode(null);
}
@Override
public boolean contains(Object x) {
if (size == 0) {
System.out.println("The list is empty!");
return false;
}
ListNode temp = header.next;
while (temp != null && !temp.element.equals(x))
temp = temp.next;
if (temp == null)
return false;
else
return true;
}
@Override
public Object getFirst() {
if (size == 0) {
System.out.println("The list is empty");
return null;
}
return header.next.element;
}
@Override
public Object getLast() {
if (size == 0) {
System.out.println("The list is empty");
return null;
}
ListNode temp = header.next;
while (temp.next != null)
temp = temp.next;
return temp.element;
}
@Override
public int getSize() {
return this.size;
}
public boolean insert(Object x) {
return insert(x, 0);
}
@Override
public boolean insert(Object x, int k) {
if (size < k)
return false;
int count = 0;
ListNode temp = header;
while (count < k && temp.next != null) {
temp = temp.next;
count++;
}
ListNode aNode = new ListNode(x);
aNode.next = temp.next;
temp.next = aNode;
size++;
return true;
}
@Override
public boolean isEmpty() {
if (size != 0)
return false;
else
return true;
}
@Override
public void makeEmpty() {
header = null;
size = 0;
}
@Override
public boolean remove(Object x) {
if (!contains(x))
return false;
ListNode temp = header;
while (temp.next != null && !temp.next.element.equals(x))
temp = temp.next;
temp.next = temp.next.next;
size--;
return true;
}
public void printList() {
if (size == 0)
System.out.println("The list is Empty");
else {
ListNode temp = header.next;
while (temp != null) {
System.out.print(temp.element + " ");
temp = temp.next;
}
}
System.out.println();
System.out.println("***************************");
}
}
3,测试类
package pku.ss.datastructure.Demo;
import pku.ss.datastructure.LinkedList.LinkedList;
public class LinkedListDemo {
public static void main(String[] args) {
LinkedList list = new LinkedList();
list.insert("H");
list.insert("G");
list.insert("F");
list.insert("E");
list.insert("D");
list.insert("C");
list.insert("B");
list.insert("A");
list.printList();
list.remove("A");
list.printList();
list.insert("D1", 3);
list.printList();
if (list.isEmpty())
System.out.println("Empty");
else
list.printList();
System.out.println("The list's size is: " + list.getSize());
System.out.println("*******************");
System.out.println("The first element is: " + list.getFirst());
System.out.println("*******************");
System.out.println("The last element is: " + list.getLast());
System.out.println("*******************");
list.makeEmpty();
if (list.isEmpty())
System.out.println("Empty");
else
list.printList();
}
}
分享到:
相关推荐
Java数据结构 线性表,链表,哈希表是常用的数据结构,在进行Java开发时,JDK已经为我们提供了一系列相应的类来实现基本的数据结构
本篇文章将深入讲解Java中链表数据结构的遍历程序,以及如何通过`LinkListFour.java`这个文件来实现链表的遍历。 首先,链表不同于数组,它不连续存储数据,而是通过节点间的引用关系构成。每个节点包含两部分:...
链表是一种基础且重要的数据结构,它在计算机科学和编程,尤其是Java中有着广泛的应用。与数组不同,链表中的元素并不在内存中连续存储,而是通过节点间的引用(或称为指针)来连接。每个节点包含两部分:数据域,...
总结一下,本主题涵盖了Java中的链表数据结构,包括`LinkedList`和`ArrayList`的实现,以及如何通过`Interface`和`Iterator`进行操作。理解这些概念对于编写高效的Java代码至关重要。通过实践和学习,你可以更好地...
在这个名为“数据结构JAVA实现”的压缩包中,我们可以看到作者提供了三种重要的数据结构——链表、有序二叉树和队列的Java代码实现。 首先,让我们详细探讨链表。链表是一种线性数据结构,与数组不同,它不连续存储...
《基于Java数据结构链表实现的“猴子选大王”》 在计算机科学中,数据结构是编程的基础,它涉及到如何高效地存储和处理数据。本文将深入探讨一个基于Java数据结构链表实现的经典问题——“猴子选大王”,也称作...
这是个java编的双向链表的演示,数据结构是编程中很重要,但很难懂的一部分
数据结构-链表 JAVA语言实现,包含单向链表、双向链表、循环链表的遍历、删除和插入 详细介绍:http://blog.csdn.net/z740852294/article/details/77369439
在编程领域,数据结构是构建高效算法的基础,而链表作为一种基本的数据结构,对于理解和掌握高级编程技巧至关重要。本文将详细探讨如何使用Java语言来实现链表,包括顺序表和单链表、双链表。 首先,我们来看顺序表...
本项目“java模拟实现数组链表树图等数据结构”旨在帮助初学者通过实际操作来理解这些基本数据结构及其工作原理。 首先,数组是最基础的数据结构,它是一个有序的元素集合,元素可以通过索引来访问。在Java中,数组...
数据结构链表是计算机科学中最为基础和重要的数据结构之一,它的灵活多变使得在数据存储、管理和操作上具有更高的效率。本文将基于Java语言来探讨链表相关程序的实现和特点,以及Java内存分配与回收机制对链表实现的...
在本项目中,“数据结构链表演示(java swing)”利用了Java Swing库来创建一个图形用户界面(GUI),直观地展示链表和堆栈的操作。 Java Swing是Java AWT(Abstract Window Toolkit)的一个扩展,提供了丰富的组件...
在Java中,双向链表是一种重要的数据结构,它允许在链表中的元素之间进行前后双向导航。本示例将详细介绍如何在Java中实现一个简单的双向链表,并提供相关的操作方法。 双向链表由一系列节点组成,每个节点包含三个...
其中,循环链表是一种常用的数据结构,它通过链式存储方式形成一个没有头尾之分的闭合结构,非常适合用来模拟这种环形排列的问题。 循环链表由一系列节点组成,每个节点包含数据和指向下一个节点的指针。在Java中,...
"Java常见数据结构面试题(带答案)" 以下是对Java常见数据结构面试题的...本篇文章主要介绍了Java常见数据结构面试题,涵盖了栈、队列、链表、线性表、树、算法、数据结构等知识点,希望对广大的程序爱好者有所帮助。
《Java数据结构和算法中文第二版》是一本深入探讨Java编程中数据结构和算法的书籍。数据结构是计算机科学的基础,它涉及到如何有效地组织和存储数据,以便在各种操作下高效地访问和修改。算法则是解决问题的具体步骤...
本话题主要探讨两种常用的数据结构——单链表和双向链表在Java中的实现,以及相关的操作,如在头部添加节点、在尾部添加节点、遍历、逆置和删除。 首先,我们来理解单链表和双向链表的基本概念。单链表是一种线性...
用java实现了数据结构中的链表,作为新手学习数据结构和java的资料。
《Java数据结构与算法》是一本深入探讨编程基础与进阶技术的书籍,其中的"applet"部分涉及了Java编程中的一个重要概念——Java小应用程序。Applet是Java语言在Web环境中的一种应用形式,它可以在浏览器中运行,为...