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

自行使用Java数组实现链表数据结构

 
阅读更多
这几年一直做企业ERP基础架构，对于算法领域的知识使用的较少，前两天被他人问及链表如何实现，草草在白板上写了一个一维字符串数组，用来表示链表，数组里面包含了一个长度为2的字符串数组，用来表示节点，节点的第一个元素保存值，第二个元素保存下个节点的引用，非常简单，但当时由于时间关系，没有仔细思考，草草作答了。

今天晚上，觉得有点时间，仔细想了下，应该采用面向对象的思想，对节点和链表高度抽象，节点应可以是任意对象。

首先让我们来复习下什么是链表？我们用一个简单的示意图表示（用画图板画了个，将就看吧:)）：



从上头可以看出，链表有如下特点：

1、有一个头和一个尾，一个有多个节点组成的非封闭的链

2、每个节点都有一个指针指向下一个节点

嗯，那我们要抽象一个链表的类，还要有一个节点的类，来实现上述链表的特点。

代码如下： 

package com.iteye.redhacker.test;

/**
 * 链表节点类
 * 
 * @author JackDou
 * @since 2013-08-11
 */
public class Node {

	private Object value;

	private Node next;

	private int index;

	public Node(Object value) {
		this.value = value;
	}

	/**
	 * @return the value
	 */
	public Object getValue() {
		return value;
	}

	/**
	 * @param value
	 *            the value to set
	 */
	public void setValue(Object value) {
		this.value = value;
	}

	/**
	 * @return the index
	 */
	public int getIndex() {
		return index;
	}

	/**
	 * @param index
	 *            the index to set
	 */
	public void setIndex(int index) {
		this.index = index;
	}

	/**
	 * @return the next
	 */
	public Node getNext() {
		return next;
	}

	/**
	 * @param next
	 *            the next to set
	 */
	public void setNext(Node next) {
		this.next = next;
	}

	@Override
	public String toString() {
		return "Node [index=" + index + "," + "value=" + value + "]";
	}
}



package com.iteye.redhacker.test;

/**
 * 链表类
 * 
 * @author JackDou
 * @since 2013-08-11
 */
public class LinkedList {
	
	/** 默认容量大小及链表容量满的时候每次自动增加的大小 */
	private static final int DEFAULT_CAPACITY_SIZE = 12;
	
	/** 链表中的节点集合 */
	private Node[] nodes;
	
	/** 指针，指向链表末端待添加的位置，默认指向0的位置 */
	private int endPos = 0;
	
	/** 当前链表容量 */
	private int capacity = 0;

	public LinkedList() {
		nodes = new Node[DEFAULT_CAPACITY_SIZE];
		capacity = DEFAULT_CAPACITY_SIZE;
	}
	
	public LinkedList(int capacity) {
		nodes = new Node[capacity];
		this.capacity = capacity;
	}
	
	/**
	 * 链表大小
	 * 
	 * @return 链表大小
	 */
	public int size() {
		return endPos;
	}
	
	public int capacity() {
		return this.nodes.length;
	}
	
	/**
	 * 向链表中加入一个节点
	 * 
	 * @param node 新加入的节点
	 */
	public void add(Node node) {
		if (this.endPos >= this.capacity() - 1) {
			capacity = this.endPos + 1 + DEFAULT_CAPACITY_SIZE;
			Node[] nodesTemp = new Node[capacity];
			System.arraycopy(nodes, 0, nodesTemp, 0, this.endPos);
			nodes = nodesTemp;
		}
		if (endPos == 0) {
			node.setIndex(0);
			nodes[endPos] = node;
		} else if (endPos > 0 && endPos <= this.capacity() - 1) {
			node.setIndex(endPos);
			nodes[endPos] = node;
			nodes[endPos-1].setNext(nodes[endPos]);
		}
		endPos++;
	}
	
	/**
	 * 删除链表元素
	 * 
	 * @param index 要删除链表中节点的位置
	 */
	public void remove(int index) {
		if (index > this.capacity() - 1 || index >= this.endPos || index < 0) {
			throw new RuntimeException("没有位置索引" + index + "存在");
		}
		if (index == endPos-1) {
			nodes[index] = null;
			return;
		}
		for (; 0 <= index && index < endPos-1; index++) {
			if (index == 0) {
				nodes[index] = nodes[index+1];
				nodes[index].setIndex(index);
			} else {
				nodes[index] = nodes[index+1];
				nodes[index].setIndex(index);
				nodes[index-1].setNext(nodes[index]);
			}
		}
		endPos--;
	}
	
	/**
	 * 更新指定链表位置节点的值
	 * 
	 * @param index 指定的链表位置
	 * @param value 指点链表位置上的节点的值
	 */
	public void update(int index, Object value) {
		if (index > this.capacity() - 1 || index >= this.endPos || index < 0) {
			throw new RuntimeException("没有位置索引" + index + "存在");
		}
		nodes[index].setValue(value);
	}
	
	/**
	 * 获取指点链表位置上的节点的值
	 * 
	 * @param index 指定的链表位置
	 * @return 指点链表位置上的节点
	 */
	public Node getNode(int index) {
		if (index > this.capacity() - 1 || index >= this.endPos || index < 0) {
			throw new RuntimeException("没有位置索引" + index + "存在");
		}
		return nodes[index];
	}
	
	/**
	 * 在链表指定位置插入节点
	 * 
	 * @param index 指定的链表位置
	 * @param value 节点
	 */
	public void insert(int index, Node node) {
		if (index > this.capacity() - 1 || index >= this.endPos || index < 0) {
			throw new RuntimeException("没有位置索引" + index + "存在");
		}
		if (this.endPos >= this.capacity() - 1) {
			capacity = this.endPos + 1 + DEFAULT_CAPACITY_SIZE;
			Node[] nodesTemp = new Node[capacity];
			System.arraycopy(nodes, 0, nodesTemp, 0, this.endPos);
			nodes = nodesTemp;
		}
		Node[] nodesTemp = new Node[size()- index];
		System.arraycopy(nodes, index, nodesTemp, 0, nodesTemp.length);

		for (int i = 0, len= nodesTemp.length; i< len; i++) {
			nodesTemp[i].setIndex(nodesTemp[i].getIndex() + 1);
		}
		endPos++;
		node.setIndex(index);
		System.arraycopy(nodesTemp, 0, nodes, index+1, nodesTemp.length);
			node.setNext(nodes[0]);
		nodes[index] = node;
		nodes[index-1].setNext(nodes[index]);
		nodes[index].setNext(nodes[index+1]);
	}
	
	/**
	 * 获取链表的第一个节点
	 * 
	 * @return 链表的第一个节点
	 */
	public Node getFirst() {
		return nodes[0];
	}
	
	/**
	 * 获取链表的最后一个节点
	 * 
	 * @return 链表的最后一个节点
	 */
	public Node getLast() {
		return nodes[endPos-1];
	}
	
	/**
	 * 链表反序
	 */
	public LinkedList reverse() {
		Node[] nodesTemp = new Node[capacity];
		for (int i = 0, j = endPos - 1; i < endPos &&  j >= 0; i++, j--) {
			nodesTemp[i] = nodes[j];
			nodesTemp[i].setIndex(i);
			if (j > 0) {
				nodesTemp[i].setNext(nodes[j-1]);
			}
		}
		nodes = nodesTemp;
		return this;
	}
	
	public String toString() {
		StringBuilder strBui = new StringBuilder();
		for (int  i = 0; i < endPos; i++) {
			strBui.append(nodes[i].toString());
			if (i < endPos) {
				strBui.append(",");
			}
		}
		return strBui.toString();
	}

	/**
	 * 获取当前链表容量
	 * 
	 * @return the capacity
	 */
	public int getCapacity() {
		return capacity;
	}
}



package com.iteye.redhacker.test;

/**
 * 测试类
 * 
 * @author JackDou
 * @since 2013-08-11
 */
public class Test {

	public static void main(String[] args) {
		// 创建默认大小的LinkedList
		LinkedList list1 = new LinkedList();
		list1.add(new Node(12));
		list1.add(new Node(10));
		list1.add(new Node(11));
		list1.add(new Node(8));
		list1.add(new Node(9));
		
		System.out.println("链表默认容量为12");
		System.out.println("链表长度：" + list1.size());
		System.out.println("链表当前容量：" + list1.getCapacity());
		System.out.println();
		
		list1.add(new Node(2));
		list1.add(new Node(4));
		list1.add(new Node(5));
		list1.add(new Node(7));
		list1.add(new Node(6));
		list1.add(new Node(1));
		list1.add(new Node(3));
		
		System.out.println("链表容量满时会自动扩容，默认为扩大12个节点容量");
		System.out.println("链表：" + list1.toString());
		System.out.println("链表第一个节点：" + list1.getFirst());
		System.out.println("链表最后一个节点节点：" + list1.getLast());
		System.out.println("链表长度：" + list1.size());
		System.out.println("链表当前容量：" + list1.getCapacity());
		System.out.println();
		
		list1.remove(3);
		System.out.println("删除索引为3的节点后的情况：");
		System.out.println("链表：" + list1.toString());
		System.out.println("链表第一个节点：" + list1.getFirst());
		System.out.println("链表最后一个节点节点：" + list1.getLast());
		System.out.println("链表长度：" + list1.size());
		System.out.println("链表当前容量：" + list1.getCapacity());
		System.out.println();
		
		list1.add(new Node(80));
		list1.add(new Node(90));
		System.out.println("新增两个节点的情况（新增：80,90两个数字）：");
		System.out.println("链表：" + list1.toString());
		System.out.println("链表第一个节点：" + list1.getFirst());
		System.out.println("链表最后一个节点节点：" + list1.getLast());
		System.out.println("链表长度：" + list1.size());
		System.out.println("链表当前容量：" + list1.getCapacity());
		System.out.println();
		
		System.out.println("获取第8个节点的信息：" + list1.getNode(8));
		System.out.println("获取第8个节点的下一个节点信息是：" + list1.getNode(8).getNext());
		System.out.println();
		
		System.out.println("测试反序链表");
		System.out.println("原链表：" + list1.toString());
		System.out.println("反序链表：" + list1.reverse().toString());
		System.out.println();
		
		System.out.println("链表长度：" + list1.size());
		System.out.println("链表当前容量：" + list1.getCapacity());
		System.out.println("测试在第3个索引的位置连续插入12个值为45的节点，使得链表长度超过当前容量，测试链表的自增长容量");
		System.out.println("原链表：" + list1.toString());
		list1.insert(3, new Node(45));
		list1.insert(3, new Node(45));
		list1.insert(3, new Node(45));
		list1.insert(3, new Node(45));
		list1.insert(3, new Node(45));
		list1.insert(3, new Node(45));
		list1.insert(3, new Node(45));
		list1.insert(3, new Node(45));
		list1.insert(3, new Node(45));
		list1.insert(3, new Node(45));
		list1.insert(3, new Node(45));
		list1.insert(3, new Node(45));
		System.out.println("插入后链表：" + list1.toString());
		System.out.println("链表长度：" + list1.size());
		System.out.println("链表当前容量：" + list1.getCapacity());
	}
}


测试类打印出来的结果是：

引用

链表默认容量为12
链表长度：5
链表当前容量：12

链表容量满时会自动扩容，默认为扩大12个节点容量
链表：Node [index=0,value=12],Node [index=1,value=10],Node [index=2,value=11],Node [index=3,value=8],Node [index=4,value=9],Node [index=5,value=2],Node [index=6,value=4],Node [index=7,value=5],Node [index=8,value=7],Node [index=9,value=6],Node [index=10,value=1],Node [index=11,value=3],
链表第一个节点：Node [index=0,value=12]
链表最后一个节点节点：Node [index=11,value=3]
链表长度：12
链表当前容量：24

删除索引为3的节点后的情况：
链表：Node [index=0,value=12],Node [index=1,value=10],Node [index=2,value=11],Node [index=3,value=9],Node [index=4,value=2],Node [index=5,value=4],Node [index=6,value=5],Node [index=7,value=7],Node [index=8,value=6],Node [index=9,value=1],Node [index=10,value=3],
链表第一个节点：Node [index=0,value=12]
链表最后一个节点节点：Node [index=10,value=3]
链表长度：11
链表当前容量：24

新增两个节点的情况（新增：80,90两个数字）：
链表：Node [index=0,value=12],Node [index=1,value=10],Node [index=2,value=11],Node [index=3,value=9],Node [index=4,value=2],Node [index=5,value=4],Node [index=6,value=5],Node [index=7,value=7],Node [index=8,value=6],Node [index=9,value=1],Node [index=10,value=3],Node [index=11,value=80],Node [index=12,value=90],
链表第一个节点：Node [index=0,value=12]
链表最后一个节点节点：Node [index=12,value=90]
链表长度：13
链表当前容量：24

获取第8个节点的信息：Node [index=8,value=6]
获取第8个节点的下一个节点信息是：Node [index=9,value=1]

测试反序链表
原链表：Node [index=0,value=12],Node [index=1,value=10],Node [index=2,value=11],Node [index=3,value=9],Node [index=4,value=2],Node [index=5,value=4],Node [index=6,value=5],Node [index=7,value=7],Node [index=8,value=6],Node [index=9,value=1],Node [index=10,value=3],Node [index=11,value=80],Node [index=12,value=90],
反序链表：Node [index=0,value=90],Node [index=1,value=80],Node [index=2,value=3],Node [index=3,value=1],Node [index=4,value=6],Node [index=5,value=7],Node [index=6,value=5],Node [index=7,value=4],Node [index=8,value=2],Node [index=9,value=9],Node [index=10,value=11],Node [index=11,value=10],Node [index=12,value=12],

链表长度：13
链表当前容量：24
测试caruso元素到第3个索引的位置连续插入12个值为45的节点，使得链表长度超过当前容量，测试链表的自增长容量
原链表：Node [index=0,value=90],Node [index=1,value=80],Node [index=2,value=3],Node [index=3,value=1],Node [index=4,value=6],Node [index=5,value=7],Node [index=6,value=5],Node [index=7,value=4],Node [index=8,value=2],Node [index=9,value=9],Node [index=10,value=11],Node [index=11,value=10],Node [index=12,value=12],
插入后链表：Node [index=0,value=90],Node [index=1,value=80],Node [index=2,value=3],Node [index=3,value=45],Node [index=4,value=45],Node [index=5,value=45],Node [index=6,value=45],Node [index=7,value=45],Node [index=8,value=45],Node [index=9,value=45],Node [index=10,value=45],Node [index=11,value=45],Node [index=12,value=45],Node [index=13,value=45],Node [index=14,value=45],Node [index=15,value=1],Node [index=16,value=6],Node [index=17,value=7],Node [index=18,value=5],Node [index=19,value=4],Node [index=20,value=2],Node [index=21,value=9],Node [index=22,value=11],Node [index=23,value=10],Node [index=24,value=12],
链表长度：25
链表当前容量：36


关于程序的详细实现这里不做详细的解释了，大家可以直接从文后下到源码，到如到eclipse里自行学习。

值得要说明的是：

1、我在链表里实现了一个反序，这是当时被问及的关键点，现在看起来似乎很简单的；
2、我在这个实现里使用了System.arraycopy()这个高级的API，或许还不够原生，有系统的同学可以实现自己的数组拷贝方法用以代替。

我的算法的复习因以此契机还需继续，希望有更多的时间去思考这些问题。加油！
  • 大小: 2.5 KB
分享到：
| openfire插件开发之完美开发
评论
2 楼 redhacker 2013-08-15  
冬天秋天 写道
啦啦 每次都提供源代码下载！

互相学习！
1 楼 冬天秋天 2013-08-12  
啦啦 每次都提供源代码下载！
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    java数组和链表数据结构的区别 数组和链表.pdf

    Java中的数组和链表是两种常见的线性数据结构，各有优缺点，适用于不同的场景。下面我们将详细探讨这两种数据结构的区别。 **数组（Array）** 数组是一种在内存中连续存储相同类型元素的数据结构。它的主要特点...

    Java数组链表效率-Java数组和链表三种遍历效率对比 数组和链表.pdf

    Java 数组链表效率对比 Java 中的数组和链表是两种常用的数据结构，它们都可以用来存储和操作数据。然而，在实际开发中，选择合适的数据结构和遍历方式对程序的性能和效率有着非常重要的影响。下面我们将对 Java 中...

    Java数组+链表简单实现HashMap的put和get 数组和链表.pdf

    在标准的Java SDK中，HashMap的实现是基于哈希表的数据结构，它内部使用数组配合链表来解决哈希冲突。这里我们将分析一个简单的自定义HashMap实现，它使用Java数组和链表来完成put和get操作。 首先，我们看到类`...

    Java用数组和链表的方式简单实现HashMap的增删改功能 数组和链表.pdf

    在Java中，HashMap的实现方式有多种，本文将介绍使用数组和链表的方式简单实现HashMap的增删改功能。 HashMap的数据结构 HashMap的数据结构主要由三个部分组成：数组、链表和红黑树。数组用于存储键值对，链表用于...

    Java基础-模拟HashMap集合（基于数组和链表） 数组和链表.pdf

    在本文中，我们将详细介绍如何模拟Java的HashMap集合，使用数组和链表来实现Hash表的存储。我们将从基本概念开始，逐步深入到HashMap的实现细节中。 什么是HashMap？ HashMap是一种基于散列表的数据结构，用于存储...

    Java集合，HashMap底层实现和原理（1.7数组+链表与1.8+的数组+链表+红黑树） 数组和链表.pdf

    在Java集合中，HashMap是一个常用的数据结构，它基于Map接口实现，元素以键值对的方式存储，并且允许使用null键和null值。由于key不允许重复，因此只能有一个键为null。HashMap不能保证插入元素的顺序，它是无序的，...

    java 动态的数组链表

    在Java编程语言中，动态数组链表是一种常见的数据结构，它结合了数组和链表的特点，既能快速访问数组中的元素，又能方便地进行插入和删除操作。本文将深入探讨Java中实现动态数组链表的关键概念、操作以及其实现方式...

    java模拟实现数组链表树图等数据结构

    本项目“java模拟实现数组链表树图等数据结构”旨在帮助初学者通过实际操作来理解这些基本数据结构及其工作原理。 首先，数组是最基础的数据结构，它是一个有序的元素集合，元素可以通过索引来访问。在Java中，数组...

    java面试编程题（数组和链表相关） 数组和链表.pdf

    本资源主要讲解了Java面试编程题中的数组和链表相关知识点，涵盖了Java编程语言中数组和链表的基本概念、算法和数据结构等方面的知识。 一、数组相关知识点 1. 、二维数组的概念和性质：在 Java 中，二维数组是一...

    数组和链表——精选推荐 数组和链表.pdf

    在Java中，Collection集合中提供了ArrayList和Vector用于数组这种数据结构的实现。 二、链表 链表是另一种常见的线性数据结构，链表由节点组成，每个节点都包含下一个节点的指针。链表有单向链表和双向链表两种。 ...

    基于JAVA实现的常用数据结构代码，JAVA实现复杂度、动态数组、链表、栈、队列、二叉搜索树等

    本压缩包"基于JAVA实现的常用数据结构代码"包含了多个关键的数据结构实现，包括复杂度分析、动态数组、链表、栈、队列以及二叉搜索树。以下是这些数据结构的详细说明： 1. **复杂度**：在计算机科学中，复杂度分为...

    Java栈的实例-数组和链表两种方法 数组和链表.pdf

    在Java中，栈可以使用两种不同的方式来实现：数组和链表。 ### 数组实现栈 数组实现栈是最基础的方式，通过预先分配一个固定大小的数组来存储栈中的元素。在`MyArrayStack`类中，数组`objs`用来存储元素，`size`...

    java中链表和数组的区别？ (1) 数组和链表.pdf

    在Java编程中，数据结构是基础，而数组和链表是两种常见的线性数据结构。它们各有特点，适用于不同的场景。下面将详细讨论这两种数据结构的区别。 首先，数组是一种静态分配内存的数据结构，其所有元素在内存中是...

    数组、单链表和双链表介绍以及双向链表的CC++Java实现 数组和链表.pdf

    数组、单链表和双链表是最基本的数据结构，它们的实现方式有所不同，但是它们都是线性表的实现方式，具有相同类型的n(n≥0)个数据元素组成的有限序列。双向链表的实现可以使用C、C++和Java三种语言，它们的实现方式...

    数组的扩容和链表结构.zip

    在Java编程语言中，数组和链表是两种基础且重要的数据结构。它们各自有独特的特点和使用场景，尤其是在处理大量数据时，理解它们的工作原理和性能特性至关重要。本压缩包文件"数组的扩容和链表结构.zip"包含了关于...

    JavaSE-数组集合和链表集合 数组和链表.docx

    数组集合是一种基本的数据结构，在Java中被广泛使用。它具有以下特点： 1. **有序性**：数组集合中的元素按照一定的顺序排列，这使得我们可以通过索引直接访问特定位置的元素。 2. **快速访问**：由于数组在内存中...

    数组 逆置-数据结构java

    数据结构的学习不仅包括数组，还有链表、栈、队列、树、图等多种类型。理解并熟练运用这些数据结构可以帮助我们设计更高效、更具可扩展性的算法。对于Java开发者来说，掌握数据结构是提高编程技能的关键步骤。通过...

    用Java动态数组扩充实现线性表

    本话题聚焦于使用动态数组来实现线性表，这是一种常见的数据结构实现方式，因为它既保留了数组的高效访问特性，又能灵活地调整大小以适应数据的变化。 动态数组，也称为可变长度数组，不同于固定大小的数组，它允许...

Magicbox
Global site tag (gtag.js) - Google Analytics