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
[]
true5. 线性表的非顺序实现——链式表
相对于数组的顺序存储，还可以定义一个比较特殊的链表结构，每个链表节点在内存中不一定是一块连续的区域，链表节点记录了与自身节点相关的下一个节点的位置信息。
如果链表节点仅仅记录了与其下一个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存储，但是添加、删除元素的时候就比较费时间，还得移动剩余元素的物理位置，使之物理连续。而双向链表的实现也不是什么省油的灯，占用资源比数组大很多，但是作为经常修改的元素集合，双向链表还是比顺序链表有性能上的优势的。