Java基礎(chǔ)復(fù)習(xí)筆記04數(shù)據(jù)結(jié)構(gòu)線性表

1、Java基礎(chǔ)復(fù)習(xí)筆記04數(shù)據(jù)結(jié)構(gòu)-線性表劉巖Email:1. 線性表線性表是數(shù)據(jù)結(jié)構(gòu)的一種邏輯結(jié)構(gòu)，其實所有的邏輯數(shù)據(jù)結(jié)構(gòu)都可以用2類物理實現(xiàn)方式去實現(xiàn)，一個是物理存儲連續(xù)的順序結(jié)構(gòu)，另一個就是物理存儲不連續(xù)的鏈式結(jié)構(gòu)。線性表是指有n個元素組成的有序序列，這n個元素具有相同的結(jié)構(gòu)。2. 線性表的操作線性表的主要操作是增加元素、刪除索引處元素、在索引處添加元素、查找索引處元素、替換索引處元素、清空所有元素。而對于順序結(jié)構(gòu)和鏈表結(jié)構(gòu)這兩種不同實現(xiàn)方式，底層的算法也會有比較大的差異。3. 使用場景其實線性表的使用場景非常多，從宏觀來說，比如我們從數(shù)據(jù)庫查詢多條記錄出來需要封裝一個集合List對象來承

2、載著眾多的業(yè)務(wù)Bean元素，之后傳給MVC的控制C層。之后C層在以某種展現(xiàn)形式傳給視圖V層。那么裝載著眾多業(yè)務(wù)記錄信息的容器就是線性表。從微觀上來講，比如實現(xiàn)數(shù)據(jù)結(jié)構(gòu)的棧結(jié)構(gòu)、或者是對象池的底層、有序排序的數(shù)據(jù)域等等比較復(fù)雜的結(jié)構(gòu)，底層都是離不開線性表的支持。4. 線性表的順序?qū)崿F(xiàn)順序表順序的存儲結(jié)構(gòu)實質(zhì)上就是利用數(shù)組進行元素的存儲，筆者簡單地實現(xiàn)了一個順序鏈表。線性表的順序?qū)崿F(xiàn)就是利用對象數(shù)組?？慈缦麓apackage dateStructer.list;/* * 自實現(xiàn)的arrayList * author liuyan * * param <E> */public class

3、 MyArrayList<E> implements List<E> /默認的數(shù)組長度private final int DefSize = 16;/臨時變量數(shù)組private Object objects;/記錄實實在在的元素個數(shù)private int elementSize;public MyArrayList() objects = new ObjectDefSize;/* * 增加元素，實際上就是往最后一位出入數(shù)據(jù) */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;/* * 實現(xiàn)元素定位 */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;/* * 對已有位置設(shè)置新的元素值 */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();實際上實現(xiàn)Java標(biāo)準的List接口還需要實現(xiàn)其他一些方法，只不過因為篇幅原因，在此只能實現(xiàn)一些核心方法，而且說實在的，根本談不上健壯性，更不可能投入使用，線程安全也存在問題，這只是演示一下用數(shù)組實現(xiàn)順序線性表的核心算法罷了。所以說學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)實際上是考驗算法

12、功底。一個數(shù)據(jù)結(jié)構(gòu)的事先是否最優(yōu)，完全是底層算法的實現(xiàn)是否最優(yōu)。順序線性表最大的特點就是物理上存儲空間連續(xù)，內(nèi)存資源使用比較節(jié)省、但是進行增加、刪除元素的時候就得讓別的元素挪挪地方了，用時間換取了空間的連續(xù)性，顯得有點牽一發(fā)而動全身。如果是查找某個元素操作的時候就是需要遍歷整體集合。 簡單測試代碼如下：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();執(zhí)行結(jié)果1,2,31,21,2,3truefalsetrue5. 線性表的非順序?qū)崿F(xiàn)鏈式表相對于數(shù)組的順序存儲，還可以定義一個比較特殊的鏈表結(jié)構(gòu)，每個鏈表節(jié)點在內(nèi)存中不一定是一塊連續(xù)的區(qū)域，鏈表節(jié)點記錄了與自身節(jié)點相關(guān)的下一個節(jié)點的位置信息。如果鏈表節(jié)點僅僅記錄了與其下一個Next節(jié)點的位置信息，而沒有記錄上一個Prev節(jié)點的信息，那么這叫做單向鏈表結(jié)構(gòu)。如果此節(jié)點不僅僅記錄了下一個節(jié)點的信息，還記錄了上一個節(jié)點的信息，那么這個情況叫做雙向鏈表結(jié)構(gòu)。我們就用雙向鏈表實現(xiàn)Java標(biāo)準的List<E>接口。（實際上Java提出了一堆標(biāo)準，實際上就是接口，而sun自己為自己定

15、義的標(biāo)準接口還提供了實現(xiàn)類，咱們一般用的就是基于sun提出標(biāo)準的sun自己的實現(xiàn)類）。如下代碼/* * 自己實現(xiàn)的linkedList * author liuyan * param <E> */public class MyLinkedList<E> implements List<E> /* * 雙向鏈表結(jié)構(gòu) */public class LinkNode / 真正的數(shù)據(jù)域private E date;/ 記錄上一個節(jié)點private LinkNode prevLinkNode;/ 記錄下一個節(jié)點private LinkNode nextLinkNode

16、;public LinkNode() public LinkNode(E date, LinkNode prevLinkNode, LinkNode nextLinkNode) this.date = date;this.prevLinkNode = prevLinkNode;this.nextLinkNode = nextLinkNode;/ 結(jié)點個數(shù)private int nodeSize;/ 頭結(jié)點private LinkNode headNode;/ 尾巴節(jié)點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;/* * 根據(jù)索引號查找節(jié)點 * * 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);/ 找到索引處的節(jié)點LinkNode linkNodeNowTemp = findLinkNodeByIndex(index);/ 找

20、出索引處節(jié)點的上一個nodeLinkNode linkNodePrev = linkNodeNowTemp.prevLinkNode;/ 上一個節(jié)點的下一個節(jié)點指向新nodelinkNodePrev.nextLinkNode = linkNodeNew;/ 新節(jié)點的上一個節(jié)點指向原位置節(jié)點上一個節(jié)點linkNodeNew.prevLinkNode = linkNodePrev;/ 新節(jié)點的下一個節(jié)點指向原位置節(jié)點linkNodeNew.nextLinkNode = linkNodeNowTemp;/ 原節(jié)點的上一個節(jié)點指向新節(jié)點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;/* * 刪除位置標(biāo)記下的元素 */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