静态数组与链表的区别以及链表的基础实现 -

LQJ2711

浏览: 5495 次
性别:

最近访客更多访客>>

娜娜TX

suifan繁

UMyeyes

yangnier

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

静态数组与链表的区别以及链表的基础实现

博客分类：

Java中级

我们初学者写程序时大多数用的是数组，但是还是有很多时候，用数组实现感觉很麻烦，所以在学习链表以后就会将这些麻烦解决了。现在我们就了解一下链表吧。
数组[非动态数组]与链表同属于数据结构，都有数据结构的基本操作，这些操作我已经在上次的动态数组的实现中说过了。
数组与链表的区别主要表现在以下几方面:
(1) 从逻辑结构角度来看
a.数组必须事先定义固定的长度（元素个数），不能适应数据动态地增减

的情况。当数据增加时，可能超出原先定义的元素个数；当数据减少时，造成内存

浪费。
b.链表动态地进行存储分配，可以适应数据动态地增减的情况，且可以方

便地插入、删除数据项。（数组中插入、删除数据项时，需要移动其它数据项）

(2)从物理存储即内存分配上分析
a.数组是连续的内存，对于访问数据，可以通过下标直接读取，时间复杂

度为O(1)，而添加删除数据就比较麻烦，需要移动操作数所在位置后的所有数据，

时间复杂度为O（N）。
b.链表是物理上非连续的内存空间，对于访问数据，需要从头便利整个链

表直到找到要访问的数据，没有数组有效，但是在添加和删除数据方面，只需要知

道操作位置的引用，很方便可以实现增删，与数组比较灵活有效率。
(3)从内存存储角度来看
a,(静态)数组从栈中分配空间, 对于程序员方便快速,但自由度小。
b, 链表从堆中分配空间, 自由度大但申请管理比较麻烦。

综合以上的一些数组与链表的特点，以及之前我写的动态数组的实现。

1.在有定长，并且查找、修改操作多且插入、删除少的就使用静态数组

2.在没有确定长度，并且查找、修改操作多且插入、删除少的就使用动态数组

3.在没有确定长度，并且插入、删除少且查找、修改操作多的就使用链表

链表的实现基础原理:

注意:

红色为改变的过程、黄色为注意事项、f表示front、d表示data、n表示next

1.增加

2.插入

3.删除

4.查找

查找的话，只能一个一个遍历查找

5.修改

只有查找到以后，才能改变该结点的值

package LQJ.newer.a1;

/**
 * 双向链表
 * 
 * @author Administrator
 *
 * @param <E>
 */
public class MyNode<E> {
	// 初始状态下，链表没有任何结点，头结点为null,尾结点为null
	private Node<E> head = null;
	private Node<E> last = null;
	//链表长度
	private int size = 0;
	/**
	 * 增加结点
	 * @param e 结点的值
	 */
	public void add(E e) {
		// 根据数据创建结点对象
		Node<E> node = new Node<E>(e);

		// 如果已经有结点，就将node作为last的下一个结点
		if (last != null) {
			last.lastnetx = node;
			node.frontnetx = last;
			last = node;
		} else {
			head = node;
			last = node;
		}
		size++;
	}
	/**
	 * 在某下标出插入某一节点(重载的增加方法)
	 * @param index 下标
	 * @param e 结点的值
	 */
	public void add(int index, E e) {
		// 构造新结点
		Node<E> node = new Node<E>(e);
		// 找到index位置的结点
		Node n1 = getNode(index);
		if (n1.equals(head)) {
			head.frontnetx = node;
			node.lastnetx = head;
			node.frontnetx = null;
			head = node;
		} else {
			// 找到index-1位置的结点
			Node n2 = n1.frontnetx;

			n2.lastnetx = node;
			node.frontnetx = n2;

			n1.frontnetx = node;
			node.lastnetx = n1;
		}
		size++;
	}
	/**
	 * 根据下标删除结点
	 * @param index 下标
	 */
	public void delete(int index) {
		Node<E> nod = getNode(index);
		//头结点与尾结点特殊处理
		if (nod.equals(head)) {
			Node<E> n = getNode(index + 1);
			n.frontnetx = null;
			head = n;
		} else if (nod.equals(last)) {
			Node<E> n = getNode(index - 1);
			n.lastnetx = null;
			last = n;
		} else {
			//找到index的前一个结点与后一个结点
			Node n1 = getNode(index - 1);
			Node n2 = getNode(index + 1);
			//引用转换
			n1.lastnetx = n2;
			n2.frontnetx = n1;
		}
		size--;

	}
	/**
	 * 根据值删除结点
	 * @param e 值
	 */
	public void delete(E e) {
		Node<E> n = head;
		Node<E> nn = last;
		//该结点的前一个结点
		Node<E> n1 = new Node<E>();
		//该结点的后一个结点
		Node<E> n2 = new Node<E>();
		//头结点与尾结点特殊处理
		if (n.data.equals(e)) {
			n = n.lastnetx;
			n.frontnetx = null;
			head = n;
		} else if (nn.data.equals(e)) {
			nn = nn.frontnetx;
			nn.lastnetx = null;
			last = nn;
		} else {
			//找到index的前一个结点与后一个结点
			while (n != null) {
				if (n.data.equals(e)) {
					n2 = n.lastnetx;
					//引用转换
					n1.lastnetx = n2;
					n2.frontnetx = n1;
					break;
				} else {
					n1 = n;
					n = n.lastnetx;
				}
			}
			if (n == null) {
				System.out.println("链表中没有找到" + e);
			}
		}
		size--;
	}
	/**
	 * 获得某值的下标
	 * @param e 值
	 * @return 下标
	 */
	private int getindex(E e) {
		int index = -1;
		Node<E> n = head;
		while (n != null) {
			index++;
			if (n.data.equals(e)) {
				break;
			}
			n = n.lastnetx;
		}
		return index;
	}
	/**
	 * 更新结点的值
	 * @param index 下标
	 * @param e 更新后的值
	 */
	public void update(int index, E e) {
		// 找到index位置的结点
		Node n1 = getNode(index);
		n1.data = e;
	}
	/**
	 * 获得某下标的值
	 * @param index 下标
	 * @return 值
	 */
	public E get(int index) {
		Node<E> node = getNode(index);
		return node.data;
	}
	/**
	 * 获得某下标的结点
	 * @param index 下标
	 * @return 结点
	 */
	public Node getnode(int index) {
		Node<E> node = getNode(index);
		return node;
	}
	/**
	 * 获得某下标的结点(私有方法)
	 * @param index 下标
	 * @return 结点
	 */
	private Node<E> getNode(int index) {
		int t = -1;
		if (index >= 0 && index < size) {
			Node<E> n = head;
			while (n != null) {
				t++;
				if (t == index) {
					break;
				}
				n = n.lastnetx;
			}
			return n;
		} else {
			// 抛出异常
			throw new IndexOutOfBoundsException("下标超出边界:" + index + size);
			// return null;
		}
	}

	public int size() {
		return size;
	}
	/**
	 * 直接正向输出
	 * @param node 头结点
	 */
	public void printfFromHead(Node node){
		//循环输出
//		while(node!=null){
//			System.out.println(node.data);
//			node=node.lastnetx;
//		}
		//递归输出
		if(node!=null){
			System.out.println(node.data);
			node=node.lastnetx;
			printfFromHead(node);
		}
	}
	/**
	 * 反向输出
	 * @param node 尾节点
	 */
	public void printfFromLast(Node node){
		while(node!=null){
			System.out.println(node.data);
			node=node.frontnetx;
		}
	}

}

/**
 * 链式结构内部结点类
 * 
 * @author Administrator
 *
 */
class Node<E> {
	// 内容
	E data;
	// 对下一个结点的引用
	Node<E> lastnetx = null;
	// 对前一个结点的引用
	Node<E> frontnetx = null;

	public Node() {
	}

	public Node(E e) {
		data = e;
	}
}