Java基础复习笔记04数据结构-线性表

1.       线性表

线性表是数据结构的一种逻辑结构，其实所有的逻辑数据结构都可以用2类物理实现方式去实现，一个是物理存储连续的顺序结构，另一个就是物理存储不连续的链式结构。线性表是指有n个元素组成的有序序列，这n个元素具有相同的结构。

2.       线性表的操作

线性表的主要操作是增加元素、删除索引处元素、在索引处添加元素、查找索引处元素、替换索引处元素、清空所有元素。而对于顺序结构和链表结构这两种不同实现方式，底层的算法也会有比较大的差异。

3.       使用场景

其实线性表的使用场景非常多，从宏观来说，比如我们从数据库查询多条记录出来需要封装一个集合List对象来承载着众多的业务Bean元素，之后传给MVC的控制C层。之后C层在以某种展现形式传给视图V层。那么装载着众多业务记录信息的容器就是线性表。从微观上来讲，比如实现数据结构的栈结构、或者是对象池的底层、有序排序的数据域等等比较复杂的结构，底层都是离不开线性表的支持。

4.       线性表的顺序实现——顺序表

顺序的存储结构实质上就是利用数组进行元素的存储，笔者简单地实现了一个顺序链表。线性表的顺序实现就是利用对象数组。

 看如下代码

 

package dateStructer.list;

/**
 * 自实现的arrayList
 * @author liuyan
 *
 * @param <E>
 */
public class MyArrayList<E> implements List<E> {
	
	//默认的数组长度
	private final int DefSize = 16;
	
	//临时变量数组
	private Object[] objects;
	
	//记录实实在在的元素个数
	private int elementSize;

	public MyArrayList() {
		objects = new Object[DefSize];
	}
	
	/**
	 * 增加元素，实际上就是往最后一位出入数据
	 */
	@Override
	public boolean add(E e) {
		add(elementSize, e);
		return true;
	}
	
	/**
	 * 按位索引插入元素
	 */
	@Override
	public void add(int index, E element) {

		if (index == elementSize) {
			objects[index] = element;
			elementSize++;
			return;
		}

		for (int i = elementSize - 1; i >= 0; i--) {

			if (i == index) {

				int movedSize = elementSize - i - 1;

				System.arraycopy(objects, index + 1, objects, index, movedSize);
				objects[index] = element;
				elementSize++;
			}

		}

	}
	
	/**
	 * 清除所有元素
	 */
	@Override
	public void clear() {
		for (int i = 0; i < elementSize; i++) {
			objects[i] = 0;
		}
		elementSize = 0;
	}
	
	/**
	 * 判断集合是否包含了某个元素
	 */
	@Override
	public boolean contains(Object o) {
		for (Object object : objects) {
			if (object != null && object.equals(o)) {
				return true;
			}
		}
		return false;
	}
	
	/**
	 * 获得某位置索引的元素
	 */
	@Override
	public E get(int index) {

		for (int i = 0; i < elementSize; i++) {
			if (i == index) {
				return (E) objects[index];
			}
		}

		return null;
	}

	/**
	 * 实现元素定位
	 */
	@Override
	public int indexOf(Object o) {

		for (int i = 0; i < elementSize; i++) {
			if (o.equals(objects[i])) {
				return i;
			}
		}
		return -1;
	}
	
	/**
	 * 是否是空集合
	 */
	@Override
	public boolean isEmpty() {

		if (elementSize == 0) {
			return true;
		}
		return false;
	}

	@Override
	public int lastIndexOf(Object o) {
		if (objects == null || objects.length == 0) {
			return -1;
		}

		for (int i = elementSize - 1; i >= 0; i--) {
			if (objects[i] == o) {
				return i;
			}
		}
		return -1;
	}
	
	/**
	 * 删除某个元素
	 */
	@Override
	public boolean remove(Object o) {

		for (int i = 0; i < elementSize; i++) {

			if (o.equals(objects[i])) {
				objects[i] = null;

				int movedSize = elementSize - i - 1;
				System.arraycopy(objects, i + 1, objects, i, movedSize);
				elementSize--;
				return true;
			}

		}

		return false;
	}
	
	/**
	 * 删除某个索引下的元素
	 */
	@Override
	public E remove(int index) {
		for (int i = 0; i < elementSize; i++) {

			if (objects[i].equals(objects[index])) {
				objects[i] = null;

				int movedSize = elementSize - i - 1;
				System.arraycopy(objects, i + 1, objects, i, movedSize);
				elementSize--;
				return (E) objects[index];
			}

		}

		return null;
	}
	
	/**
	 * 对已有位置设置新的元素值
	 */
	@Override
	public E set(int index, E element) {

		for (int i = 0; i < elementSize; i++) {

			if (i == index) {
				objects[index] = null;
				objects[index] = element;
				return element;
			}

		}

		return null;
	}

	@Override
	public int size() {
		// TODO Auto-generated method stub
		return elementSize;
	}

	@Override
	public String toString() {

		StringBuffer str = new StringBuffer("[");

		for (int i = 0; i < elementSize; i++) {

			str.append("[" + objects[i].toString() + "],");

		}

		if (elementSize > 0) {
			return str.substring(0, str.lastIndexOf(",")) + "]";
		}

		return str.append("]").toString();
	}

 实际上实现Java标准的List接口还需要实现其他一些方法，只不过因为篇幅原因，在此只能实现一些核心方法，而且说实在的，根本谈不上健壮性，更不可能投入使用，线程安全也存在问题，这只是演示一下用数组实现顺序线性表的核心算法罢了。所以说学习数据结构实际上是考验算法功底。一个数据结构的事先是否最优，完全是底层算法的实现是否最优。顺序线性表最大的特点就是物理上存储空间连续，内存资源使用比较节省、但是进行增加、删除元素的时候就得让别的元素挪挪地方了，用时间换取了空间的连续性，显得有点牵一发而动全身。如果是查找某个元素操作的时候就是需要遍历整体集合。

简单测试代码如下：

	public static void main(String[] args) {
		MyArrayList<String> list = new MyArrayList<String>();
		list.add("1");
		list.add("2");
		list.add("3");
		System.out.println(list);
		list.remove("3");
		System.out.println(list);
		list.add("3");
		System.out.println(list);
		System.out.println(list.contains("2"));
		System.out.println(list.isEmpty());
		list.clear();
		System.out.println(list);
		System.out.println(list.isEmpty());
	}

 执行结果

[[1],[2],[3]]
[[1],[2]]
[[1],[2],[3]]
true
false
[]
true

 5.       线性表的非顺序实现——链式表

相对于数组的顺序存储，还可以定义一个比较特殊的链表结构，每个链表节点在内存中不一定是一块连续的区域，链表节点记录了与自身节点相关的下一个节点的位置信息。

如果链表节点仅仅记录了与其下一个Next节点的位置信息，而没有记录上一个Prev节点的信息，那么这叫做单向链表结构。

如果此节点不仅仅记录了下一个节点的信息，还记录了上一个节点的信息，那么这个情况叫做双向链表结构。我们就用双向链表实现Java标准的List<E>接口。（实际上Java提出了一堆标准，实际上就是接口，而sun自己为自己定义的标准接口还提供了实现类，咱们一般用的就是基于sun提出标准的sun自己的实现类）。

 如下代码

/**
 * 自己实现的linkedList
 * @author liuyan
 * @param <E>
 */
public class MyLinkedList<E> implements List<E> {

	/**
	 * 双向链表结构
	 */
	public class LinkNode {

		// 真正的数据域
		private E date;

		// 记录上一个节点
		private LinkNode prevLinkNode;

		// 记录下一个节点
		private LinkNode nextLinkNode;

		public LinkNode() {

		}

		public LinkNode(E date, LinkNode prevLinkNode, LinkNode nextLinkNode) {
			this.date = date;
			this.prevLinkNode = prevLinkNode;
			this.nextLinkNode = nextLinkNode;
		}
	}

	// 结点个数
	private int nodeSize;

	// 头结点
	private LinkNode headNode;

	// 尾巴节点
	private LinkNode tailNode;

	public MyLinkedList() {
		headNode = null;
		tailNode = null;
	}

	/**
	 * 采用尾端元素增加法，增加新元素
	 */
	@Override
	public boolean add(E element) {
		if (nodeSize == 0) {
			headNode = new LinkNode(element, null, tailNode);
		} else {

			if (tailNode == null) {
				tailNode = new LinkNode(element, headNode, null);
				headNode.nextLinkNode = tailNode;
				nodeSize++;
				return true;
			}

			LinkNode linkNode = tailNode;
			tailNode = new LinkNode(element, linkNode, null);
			linkNode.nextLinkNode = tailNode;

		}
		nodeSize++;
		return true;
	}

	/**
	 * 根据索引号查找节点
	 * 
	 * @param index
	 * @return
	 */
	public LinkNode findLinkNodeByIndex(int index) {

		LinkNode linkNodeNowTemp = headNode;

		for (int i = 0; i < nodeSize; i++) {

			if (i == index) {
				return linkNodeNowTemp;
			}

			linkNodeNowTemp = linkNodeNowTemp.nextLinkNode;
		}
		return null;
	}
	
	/**
	 * 按索引位置添加元素
	 */
	@Override
	public void add(int index, E element) {

		if (nodeSize == 0) {
			add(element);
		}

		// 按照元素先建立新的node
		LinkNode linkNodeNew = new LinkNode(element, null, null);

		// 找到索引处的节点
		LinkNode linkNodeNowTemp = findLinkNodeByIndex(index);

		// 找出索引处节点的上一个node
		LinkNode linkNodePrev = linkNodeNowTemp.prevLinkNode;

		// 上一个节点的下一个节点指向新node
		linkNodePrev.nextLinkNode = linkNodeNew;

		// 新节点的上一个节点指向原位置节点上一个节点
		linkNodeNew.prevLinkNode = linkNodePrev;

		// 新节点的下一个节点指向原位置节点
		linkNodeNew.nextLinkNode = linkNodeNowTemp;

		// 原节点的上一个节点指向新节点
		linkNodeNowTemp.prevLinkNode = linkNodeNew;
		
		nodeSize ++;
	}

	/**
	 * 清除所有Node元素资源
	 */
	@Override
	public void clear() {

		LinkNode linkNodeNowTemp = headNode;

		for (int i = 0; i < nodeSize; i++) {

			if (linkNodeNowTemp != tailNode && linkNodeNowTemp != headNode) {
				linkNodeNowTemp = linkNodeNowTemp.nextLinkNode;
				linkNodeNowTemp.prevLinkNode.nextLinkNode = null;
				linkNodeNowTemp.prevLinkNode.prevLinkNode = null;
				linkNodeNowTemp.prevLinkNode.date = null;
				linkNodeNowTemp.prevLinkNode = null;
			} else if (linkNodeNowTemp == tailNode) {
				linkNodeNowTemp.prevLinkNode = null;
			} else if (linkNodeNowTemp == headNode) {
				linkNodeNowTemp.nextLinkNode = null;
			}

		}
		headNode = null;
		tailNode = null;
		nodeSize = 0;

	}
	
	/**
	 * 是否包含此元素
	 */
	@Override
	public boolean contains(Object object) {

		LinkNode linkNodeNowTemp = headNode;

		for (int i = 0; i < nodeSize; i++) {

			if (object == linkNodeNowTemp.date) {
				return true;
			}

			linkNodeNowTemp = linkNodeNowTemp.nextLinkNode;
		}

		return false;
	}

	@Override
	public E get(int index) {

		LinkNode linkNode = findLinkNodeByIndex(index);

		if (linkNode != null) {
			return linkNode.date;
		}

		return null;
	}

	@Override
	public boolean isEmpty() {
		return nodeSize == 0;
	}

	/**
	 * 删除元素
	 */
	@Override
	public boolean remove(Object o) {

		LinkNode linkNodeNowTemp = headNode;

		for (int i = 0; i < nodeSize; i++) {

			if (linkNodeNowTemp.date == o) {

				if (linkNodeNowTemp != tailNode && linkNodeNowTemp != headNode) {
					LinkNode linkNewPrev = linkNodeNowTemp.prevLinkNode;
					LinkNode linkNewNext = linkNodeNowTemp.nextLinkNode;
					linkNewPrev.nextLinkNode = linkNewNext;
					linkNewNext.prevLinkNode = linkNewPrev;

					linkNodeNowTemp.nextLinkNode = null;
					linkNodeNowTemp.prevLinkNode = null;
					linkNodeNowTemp.date = null;
					linkNodeNowTemp = null;
					nodeSize--;
					return true;
				} else if (linkNodeNowTemp == tailNode) {
					tailNode = linkNodeNowTemp.prevLinkNode;

					linkNodeNowTemp.prevLinkNode = null;
					linkNodeNowTemp.date = null;
					linkNodeNowTemp = null;
					nodeSize--;
					return true;
				} else if (linkNodeNowTemp == headNode) {
					headNode = linkNodeNowTemp.nextLinkNode;

					linkNodeNowTemp.nextLinkNode = null;
					linkNodeNowTemp.date = null;
					linkNodeNowTemp = null;
					nodeSize--;
					return true;
				}

			}

			linkNodeNowTemp = linkNodeNowTemp.nextLinkNode;
		}

		return false;
	}

	/**
	 * 删除位置标记下的元素
	 */
	@Override
	public E remove(int index) {

		LinkNode linkNodeNowTemp = headNode;

		for (int i = 0; i < nodeSize; i++) {

			if (index == i) {
				LinkNode linkNewPrev = linkNodeNowTemp.prevLinkNode;
				LinkNode linkNewNext = linkNodeNowTemp.nextLinkNode;
				linkNewPrev.nextLinkNode = linkNewNext;
				linkNewNext.prevLinkNode = linkNewPrev;

				linkNodeNowTemp.nextLinkNode = null;
				linkNodeNowTemp.prevLinkNode = null;
				linkNodeNowTemp.date = null;
				linkNodeNowTemp = null;
				break;
			}

			linkNodeNowTemp = linkNodeNowTemp.nextLinkNode;
		}

		return null;
	}

	@Override
	public int size() {
		// TODO Auto-generated method stub
		return nodeSize;
	}

	@Override
	public String toString() {

		StringBuffer str = new StringBuffer("[");
		LinkNode linkNode = null;
		for (int i = 0; i < nodeSize; i++) {

			linkNode = findLinkNodeByIndex(i);

			str.append("[" + linkNode.date + "],");

		}

		if (nodeSize > 0) {
			return str.substring(0, str.lastIndexOf(",")) + "]";
		}

		return str.append("]").toString();
	}
}

 和顺序实现一样，实现了核心方法，测试代码相同。

6.       总结

这次总结了线性表的数据结构，并且用数组和双向链表节点实现了类似ArrayList和LinkedList的功能。主要是实现了核心的方法。为了节省资源，一般使用ArrayList存储，但是添加、删除元素的时候就比较费时间，还得移动剩余元素的物理位置，使之物理连续。而双向链表的实现也不是什么省油的灯，占用资源比数组大很多，但是作为经常修改的元素集合，双向链表还是比顺序链表有性能上的优势的。