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

1、Java基础复习笔记04数据结构-线性表刘岩Email:1. 线性表线性表是数据结构的一种逻辑结构，其实所有的逻辑数据结构都可以用2类物理实现方式去实现，一个是物理存储连续的顺序结构，另一个就是物理存储不连续的链式结构。线性表是指有n个元素组成的有序序列，这n个元素具有相同的结构。2. 线性表的操作线性表的主要操作是增加元素、删除索引处元素、在索引处添加元素、查找索引处元素、替换索引处元素、清空所有元素。而对于顺序结构和链表结构这两种不同实现方式，底层的算法也会有比较大的差异。3. 使用场景其实线性表的使用场景非常多，从宏观来说，比如我们从数据库查询多条记录出来需要封装一个集合List对象来承

2、载着众多的业务Bean元素，之后传给MVC的控制C层。之后C层在以某种展现形式传给视图V层。那么装载着众多业务记录信息的容器就是线性表。从微观上来讲，比如实现数据结构的栈结构、或者是对象池的底层、有序排序的数据域等等比较复杂的结构，底层都是离不开线性表的支持。4. 线性表的顺序实现顺序表顺序的存储结构实质上就是利用数组进行元素的存储，笔者简单地实现了一个顺序链表。线性表的顺序实现就是利用对象数组。看如下代码package dateStructer.list;/* * 自实现的arrayList * author liuyan * * param <E> */public class

3、 MyArrayList<E> implements List<E> /默认的数组长度private final int DefSize = 16;/临时变量数组private Object objects;/记录实实在在的元素个数private int elementSize;public MyArrayList() objects = new ObjectDefSize;/* * 增加元素，实际上就是往最后一位出入数据 */Overridepublic boolean add(E e) add(elementSize, e);return true;/* * 按位索

4、引插入元素 */Overridepublic void add(int index, E element) if (index = elementSize) objectsindex = 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);objectsindex = ele

5、ment;elementSize+;/* * 清除所有元素 */Overridepublic void clear() for (int i = 0; i < elementSize; i+) objectsi = 0;elementSize = 0;/* * 判断集合是否包含了某个元素 */Overridepublic boolean contains(Object o) for (Object object : objects) if (object != null && object.equals(o) return true;return false;/* * 获

6、得某位置索引的元素 */Overridepublic E get(int index) for (int i = 0; i < elementSize; i+) if (i = index) return (E) objectsindex;return null;/* * 实现元素定位 */Overridepublic int indexOf(Object o) for (int i = 0; i < elementSize; i+) if (o.equals(objectsi) return i;return -1;/* * 是否是空集合 */Overridepublic boo

7、lean isEmpty() if (elementSize = 0) return true;return false;Overridepublic int lastIndexOf(Object o) if (objects = null | objects.length = 0) return -1;for (int i = elementSize - 1; i >= 0; i-) if (objectsi = o) return i;return -1;/* * 删除某个元素 */Overridepublic boolean remove(Object o) for (int i

8、= 0; i < elementSize; i+) if (o.equals(objectsi) objectsi = null;int movedSize = elementSize - i - 1;System.arraycopy(objects, i + 1, objects, i, movedSize);elementSize-;return true;return false;/* * 删除某个索引下的元素 */Overridepublic E remove(int index) for (int i = 0; i < elementSize; i+) if (objec

9、tsi.equals(objectsindex) objectsi = null;int movedSize = elementSize - i - 1;System.arraycopy(objects, i + 1, objects, i, movedSize);elementSize-;return (E) objectsindex;return null;/* * 对已有位置设置新的元素值 */Overridepublic E set(int index, E element) for (int i = 0; i < elementSize; i+) if (i = index)

10、objectsindex = null;objectsindex = element;return element;return null;Overridepublic int size() / TODO Auto-generated method stubreturn elementSize;Overridepublic String toString() StringBuffer str = new StringBuffer("");for (int i = 0; i < elementSize; i+) str.append("" + obj

11、ectsi.toString() + ",");if (elementSize > 0) return str.substring(0, str.lastIndexOf(",") + ""return str.append("").toString();实际上实现Java标准的List接口还需要实现其他一些方法，只不过因为篇幅原因，在此只能实现一些核心方法，而且说实在的，根本谈不上健壮性，更不可能投入使用，线程安全也存在问题，这只是演示一下用数组实现顺序线性表的核心算法罢了。所以说学习数据结构实际上是考验算法

12、功底。一个数据结构的事先是否最优，完全是底层算法的实现是否最优。顺序线性表最大的特点就是物理上存储空间连续，内存资源使用比较节省、但是进行增加、删除元素的时候就得让别的元素挪挪地方了，用时间换取了空间的连续性，显得有点牵一发而动全身。如果是查找某个元素操作的时候就是需要遍历整体集合。 简单测试代码如下：public static void main(String args) MyArrayList<String> list = new MyArrayList<String>();list.add("1");list.add("2"

13、);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.isEm

14、pty();执行结果1,2,31,21,2,3truefalsetrue5. 线性表的非顺序实现链式表相对于数组的顺序存储，还可以定义一个比较特殊的链表结构，每个链表节点在内存中不一定是一块连续的区域，链表节点记录了与自身节点相关的下一个节点的位置信息。如果链表节点仅仅记录了与其下一个Next节点的位置信息，而没有记录上一个Prev节点的信息，那么这叫做单向链表结构。如果此节点不仅仅记录了下一个节点的信息，还记录了上一个节点的信息，那么这个情况叫做双向链表结构。我们就用双向链表实现Java标准的List<E>接口。（实际上Java提出了一堆标准，实际上就是接口，而sun自己为自己定

15、义的标准接口还提供了实现类，咱们一般用的就是基于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

16、;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;

17、tailNode = null;/* * 采用尾端元素增加法，增加新元素 */Overridepublic 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 = tailN

18、ode;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 linkNode

19、NowTemp;linkNodeNowTemp = linkNodeNowTemp.nextLinkNode;return null;/* * 按索引位置添加元素 */Overridepublic void add(int index, E element) if (nodeSize = 0) add(element);/ 按照元素先建立新的nodeLinkNode linkNodeNew = new LinkNode(element, null, null);/ 找到索引处的节点LinkNode linkNodeNowTemp = findLinkNodeByIndex(index);/ 找

20、出索引处节点的上一个nodeLinkNode linkNodePrev = linkNodeNowTemp.prevLinkNode;/ 上一个节点的下一个节点指向新nodelinkNodePrev.nextLinkNode = linkNodeNew;/ 新节点的上一个节点指向原位置节点上一个节点linkNodeNew.prevLinkNode = linkNodePrev;/ 新节点的下一个节点指向原位置节点linkNodeNew.nextLinkNode = linkNodeNowTemp;/ 原节点的上一个节点指向新节点linkNodeNowTemp.prevLinkNode = li

21、nkNodeNew;nodeSize +;/* * 清除所有Node元素资源 */Overridepublic void clear() LinkNode linkNodeNowTemp = headNode;for (int i = 0; i < nodeSize; i+) if (linkNodeNowTemp != tailNode && linkNodeNowTemp != headNode) linkNodeNowTemp = linkNodeNowTemp.nextLinkNode;linkNodeNowTemp.prevLinkNode.nextLinkNo

22、de = 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;

23、tailNode = null;nodeSize = 0;/* * 是否包含此元素 */Overridepublic 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;Overridepublic E get(int inde

24、x) LinkNode linkNode = findLinkNodeByIndex(index);if (linkNode != null) return linkNode.date;return null;Overridepublic boolean isEmpty() return nodeSize = 0;/* * 删除元素 */Overridepublic boolean remove(Object o) LinkNode linkNodeNowTemp = headNode;for (int i = 0; i < nodeSize; i+) if (linkNodeNowTe

25、mp.date = o) if (linkNodeNowTemp != tailNode && linkNodeNowTemp != headNode) LinkNode linkNewPrev = linkNodeNowTemp.prevLinkNode;LinkNode linkNewNext = linkNodeNowTemp.nextLinkNode;linkNewPrev.nextLinkNode = linkNewNext;linkNewNext.prevLinkNode = linkNewPrev;linkNodeNowTemp.nextLinkNode = nu

26、ll;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;

27、else if (linkNodeNowTemp = headNode) headNode = linkNodeNowTemp.nextLinkNode;linkNodeNowTemp.nextLinkNode = null;linkNodeNowTemp.date = null;linkNodeNowTemp = null;nodeSize-;return true;linkNodeNowTemp = linkNodeNowTemp.nextLinkNode;return false;/* * 删除位置标记下的元素 */Overridepublic E remove(int index) L

28、inkNode 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 =

29、null;linkNodeNowTemp.prevLinkNode = null;linkNodeNowTemp.date = null;linkNodeNowTemp = null;break;linkNodeNowTemp = linkNodeNowTemp.nextLinkNode;return null;Overridepublic int size() / TODO Auto-generated method stubreturn nodeSize;Overridepublic String toString() StringBuffer str = new StringBuffer("");LinkNode linkNode = null;for (int i = 0; i < nodeSize; i+) li