`

数组和链表的区别及使用场景

阅读更多
Java中已经定义好了一个长度可变数组:ArrayList

数组的特点:内存地址连续

优点:数据是存放在一个连续的内存地址上,查找效率比较高

缺点:在改变数据个数的时候[增加,插入,删除]效率比较低

链式列表:[链表] 数据在内存中可以在任意位置,通过引用来关联数据

1.MyArray 数组
package com.newer.cjl.api;

/**
 * 自定义长度可变的数组[泛型]
 * 
 * @author Administrator
 * 
 */
public class MyArray<E> {

	// 定义一个长度为0的初始数组
	private Object[] src = new Object[0];

	/**
	 * 存放数据
	 * 
	 * @param s
	 *            要存放的数据
	 */
	public void add(E s) {
		// 定义一个新数组长度是源数组长度+1
		Object[] dest = new Object[src.length + 1];
		// 将原数组的数据拷贝到新数组中
		System.arraycopy(src, 0, dest, 0, src.length);
		// 将新数据放到新数组的最后一个位置
		dest[dest.length - 1] = s;
		// 将原数组指向新数组
		src = dest;

	}

	/**
	 * 取出数据
	 * 
	 * @param index
	 *            要取出的数据的下标
	 */
	public E get(int index) {
		Object s = src[index];
		return (E)s;
	}

	/**
	 * 根据下标删除数据
	 * 
	 * @param index
	 *            要删除的数据的下标
	 */
	public void delete(int index) {
		Object[] dest = new Object[src.length-1];
		//将下标小于index的拷贝到新数组对应的下标位置
		System.arraycopy(src, 0, dest, 0, index);
		
		//将下标大于index的拷贝到新数组下标的位置为原数组的下标位置-1
		System.arraycopy(src, index+1, dest, index, src.length-index-1);
		//将src指向新数组
		src=dest;
	}

	/**
	 * 删除指定的数据
	 * 
	 * @param s
	 *            要删除的数据,如果有重复的数据,就删除下标最小的
	 */
	public void delete(E s) {
		int t=-1;
		for(int i=0;i<src.length;i++){
			if(src[i].equals(s)){
				t=i;
				break;
			}
		}
		//如果s在数组中出现过,t一定会>=0
		if(t>=0){
			delete(t);
		}
	}

	/**
	 * 将数据插入到指定位置
	 * @param index 要插入的位置
	 * @param s 要插入的数据
	 */
	public void insert(int index,E s){
		Object[] dest = new Object[src.length+1];
		//将新数据放到新数组的指定位置
		dest[index]=s;
		
		//将下标小于index的数据拷贝到新数组对应的下标位置
		System.arraycopy(src, 0, dest, 0, index);
		//将下标>=index的数据宝贝到新数组下标+1的位置
		System.arraycopy(src, index, dest, index+1, src.length-index);
		
		src=dest;
		
	}
	
	/**
	 * 修改数据
	 * 
	 * @param index
	 *            要修改的数据的下标
	 * @param s
	 *            修改后的数据
	 */
	public void update(int index, E s) {
		src[index] = s;
	}

	/**
	 * 获得数据个数
	 */
	public int size() {
		return src.length;
	}
}

2.Main主函数实现
package com.newer.cjl.api;

import java.util.ArrayList;

/**
 * 自定义长度可变数组的测试类
 * 
 * @author Administrator
 * 
 */
public class Main {

	public static void main(String[] args) {
//		// 创建数组对象
//		MyArray<String> arr = new MyArray<String>();
//		// 增加数据
//		arr.add("AA");
//		arr.add("BB");
//		arr.add("CC");
//		arr.add("DD");
//		arr.add("EE");
//		arr.add("FF");
//		
//		
//		arr.insert(5, "新来的");
//		
//		// 取出数据
//		for (int i = 0; i < arr.size(); i++) {
//			String s = arr.get(i);
//			System.out.println(s);
//		}
		
		
		ArrayList<Integer> arr = new ArrayList<Integer>();
		arr.add(100);
		arr.add(200);
		arr.add(300);

		for(int i=0;i<arr.size();i++){
			int t = arr.get(i);
			System.out.println(t);
		}
		
	}
}

3.双向链表
package com.newer.cjl.api;

/**
 * 自定义链表类【双向链表】
 * 
 * @author Administrator
 * 
 */
public class MyLinkList<E> {

	// 初始状态下,链表没有任何结点,头结点为null,尾结点为null
	private Node<E> head = null;
	private Node<E> last = null;
	private int num = 0;// 数据个数

	// 增加数据
	public void add(E e) {
		// 根据数据创建结点对象
		Node<E> node = new Node<E>(e);

		// 如果链表中已经有结点,就将node作为last的下一个结点
		if (last != null) {
			last.next = node;
			node.front = last;
			last = node;
		} else {
			// 如果链表中还没有结点,node就是第一个结点
			// 既是头结点,又是尾结点
			head = node;
			last = node;
		}
		num++;

	}

	public void insert(int index, E e) {
		// 创建新结点
		Node<E> node = new Node<E>(e);
		// 找到index位置的结点
		Node<E> n1 = getNode(index);
		// 找到n1的前一个结点
		Node<E> n2 = n1.front;

		n2.next = node;
		node.front = n2;

		node.next = n1;
		n1.front = node;

		num++;
	}

	public void delete(int index) {

	}

	public void delete(E e) {

	}

	public void update(int index, E e) {
		Node<E> n1 = getNode(index);
		n1.data = e;
	}

	public E get(int index) {
		Node<E> node = getNode(index);
		return node.data;
	}

	//根据内容确定下标
	private int getIndex(E e){
		int index=-1;
		Node<E> n = head;
		while(n!=null){
			index++;
			if(n.data.equals(e)){
				break;
			}
			n=n.next;
		}
		return index;
	}
	
	public int getIndex2(E e){
		for(int i=0;i<num;i++){
			E e2 = get(i);
			if(e2.equals(e)){
				return i;
			}
		}
		return -1;
		
	}
	
	//根据下标确定结点
	private Node<E> getNode(int index) {
		int t = -1;
		if (index >= 0 && index < num) {
			Node<E> n = head;

			while (n != null) {
				t++;
				if (t == index) {
					break;
				}
				n = n.next;

			}
			return n;

		} else {
			// 抛出异常
			throw new IndexOutOfBoundsException("下标超出边界!index:" + index
					+ ",size:" + num);
		}
	}
	

	public int size() {
		return num;
	}

}

// 内部的结点类,主要为MyLinkList类服务
class Node<E> {
	// 结点的数据
	E data;
	// 对下一个结点的引用
	Node<E> next;
	// 对前一个结点的引用
	Node<E> front;

	// 创建结点对象的时候必须指定数据
	public Node(E e) {
		data = e;
	}

}

4、主函数Main实现
package com.newer.cjl.api;

public class Main4 {

	public static void main(String[] args) {
		MyLinkList<String> list = new MyLinkList<String>();

		list.add("AA");
		list.add("BB");
		list.add("CC");
		list.add("BB");
		list.add("DD");

		// //测试add方法是否正确
		// System.out.println(list.last.data);
		// Node<String> node = list.last.front;
		// while(node!=null){
		// System.out.println(node.data);
		// node = node.front;
		//
		// }

//		list.insert(2, "EE");
//		list.update(3, "FF");
//		
//		for (int i = 0; i < list.size(); i++) {
//			String s = list.get(i);
//			System.out.println(s);
//		}
		
		int t = list.getIndex2("BB");
		System.out.println(t);
	}

}
分享到:
评论

相关推荐

    数组和链表的使用场景 数组和链表.pdf

    数组和链表的使用场景 在计算机科学中,数组和链表是两种基本的数据结构,它们都是线性表的实现方式,但它们有着不同的存储结构和访问方式,从而导致不同的使用场景。 数组是一种连续存储的数据结构,即在内存中...

    遍历数组和链表 数组和链表.pdf

    在实际应用中,数组和链表有着不同的使用场景。数组适合静态存储,动态添加,内存为一连续的地址,查询较快,而链表适合动态存储,扩展性强,只能顺着指针的方向查询,速度较慢。 我们可以得出结论:数组大小固定,...

    面试题总结:数组和链表的区别 数组和链表.pdf

    然而,数组和链表有着根本的区别,这些区别决定了它们在不同的场景下的应用。 数组 数组是一种连续存储的数据结构,即数组中的元素在内存中是连续存储的。这使得数组在查找数据时效率非常高,因为内存地址是连续的...

    pythonlist是数组还是链表实现的-数组和链表结构(python)-1 数组和链表.pdf

    -数组和链表结构(Python)" Python列表是一个非常常用的数据结构,但是它究竟是数组还是链表实现的?在Python中,列表是使用链表结构实现的,但是在某些情况下,也可以使用数组结构来实现。那么,为什么Python列表...

    数组和链表(使用场景和反转链表) 数组和链表.pdf

    数组和链表是两种基本且常用的数据结构,它们各有优缺点,适用于不同的场景。 数组是一种顺序存储结构,它在内存中占据一块连续的空间。数组的主要优点在于其随机访问的高效性,可以通过索引直接访问任意位置的元素...

    数组和链表的对比分析 数组和链表.docx

    与数组不同,链表中的元素不一定是连续存储的,这使得插入和删除操作更加灵活和高效。然而,由于链表中的元素不是直接通过索引访问的,因此访问特定元素通常需要从头节点开始逐个遍历,这可能导致效率较低。 #### ...

    数组和链表分别比较适合用于什么场景 数组和链表.pdf

    数组和链表是两种基本的数据结构,它们各自有其适用的场景和特点。在计算机科学中,选择合适的数据结构对于程序的效率和性能至关重要。 数组是一种线性数据结构,它在内存中以连续的方式存储元素。这意味着数组的...

    c语言数组与链表转化-分别用数组和链表实现堆栈(C语言版)(转) 数组和链表.pdf

    本资源主要讲解了使用C语言实现堆栈的两种方法:使用数组和链表。堆栈是一种常用的数据结构,它可以用来实现递归算法、表达式求值、语法分析等。 第一种方法是使用数组实现堆栈。在这种方法中,我们需要定义一个...

    数组和链表和集合的区别和应用场景以及堆和栈的区别 数组和链表.pdf

    数组、链表和集合的区别和应用场景以及堆和栈的区别 数组和集合的区别: 1. 数组的长度是固定的,而集合的长度是动态不固定的。 2. 数组的存储类型是单一的,同一个数组只能存储同一数据类型的数据,而集合可以...

    数组与链表的区别

    数组适合于数据量固定、访问频率较高的场景,而链表则更适合于数据量动态变化较大、需要频繁插入和删除的场合。理解它们的区别有助于我们在实际开发中选择最合适的数据结构来解决问题。在选择合适的数据结构时,还...

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

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

    go语言通过数组和链表的方式实现队列 数组和链表.pdf

    "go语言通过数组和链表的方式实现队列" 从给定的文件信息中,我们可以生成以下知识点: 1.队列的定义:队列是一种特殊的线性表,只能在队列的尾部添加元素,在队列的头部删除元素,先进先出(FIFO)。 2.go语言中...

    php数组当链表-php数组和链表的区别总结 数组和链表.pdf

    下面是对PHP数组和链表之间区别的详细解释。 1. **逻辑结构** - **数组**:数组是一种线性数据结构,其所有元素在内存中是连续存储的。在PHP中,数组可以存储不同类型的数据,并且可以通过索引(下标)快速访问。...

    用C数组和链表实现的学生成绩管理系统

    在编程领域,数组和链表是两种基础但重要的数据结构,它们在实现各种系统和算法时发挥着关键作用。在这个“学生成绩管理系统”中,我们看到了如何利用这两种数据结构来存储和操作学生成绩。下面我们将深入探讨这两个...

    数组和链表的区别和优缺点总结! 数组和链表.pdf

    数组和链表的区别和优缺点总结 数组和链表是两种基本的数据结构,它们在内存存储上的表现不一样,所以也有各自的特点。 数组的特点: * 数组是连续的内存区域,需要预留空间,在使用前要先申请占内存的大小,可能...

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

    Java集合,HashMap底层实现和原理(1.7数组+链表与1.8+的数组+链表+红黑树) 在Java集合中,HashMap是一个常用的数据结构,它基于Map接口实现,元素以键值对的方式存储,并且允许使用null键和null值。由于key不允许...

    数据结构:数组和链表的区别以及各自的优缺点 数组和链表.pdf

    "数据结构:数组和链表的区别以及各自的优缺点" 数据结构是计算机科学中研究的基本概念之一,数组和链表是两种最基本的数据结构形式。它们在计算机科学和其他相关领域中发挥着重要的作用。 数组是将元素在内存中...

    集合(链表和数组的区别) 数组和链表.pdf

    这种差异会影响到数组和链表的使用场景。 2. 内存布局 数组在内存中是连续的,即数组的每个元素在内存中是相邻的。链表在内存中是不连续的,即链表的每个元素在内存中的地址是随机的。这也会影响到数组和链表的...

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

    "数组和链表" 数组和链表是两种常见的线性数据结构,它们都是由具有相同类型的n(n≥0)个数据元素组成的有限序列。...数组和链表是两种常见的线性数据结构,它们各自的优缺点,选择哪种数据结构取决于具体的应用场景。

    数组和链表的区别 (2) 数组和链表.pdf

    数组和链表是两种基本的数据结构,它们在存储和操作数据方面有着显著的区别。理解这些差异对于优化算法和设计高效的数据结构至关重要。 首先,数组是一种将同一类型的数据元素集合在一起的数据结构。每个元素都有一...

Global site tag (gtag.js) - Google Analytics