1. 概要

線性表是一種線性結構，它是具有相同類型的n(n≥0)個數據元素組成的有限序列。本章先介紹線性表的幾個基本組成部分：數組、單向鏈表、雙向鏈表；隨后給出雙向鏈表的C、C++和Java三種語言的實現

2. 數組

數組有上界和下界，數組的元素在上下界內是連續的。存儲10,20,30,40,50的數組的示意圖如下

數組的特點是：數據是連續的；隨機訪問速度快。

數組中稍微復雜一點的是多維數組和動態數組。對于C語言而言，多維數組本質上也是通過一維數組實現的。至于動態數組，是指數組的容量能動態增長的數組；對于C語言而言，若要提供動態數組，需要手動實現；而對于C++而言，STL提供了Vector；對于Java而言，Collection集合中提供了ArrayList和Vector。

3. 單向鏈表

單向鏈表(單鏈表)是鏈表的一種，它由節點組成，每個節點都包含下一個節點的指針。

單鏈表的示意圖如下：

表頭為空，表頭的后繼節點是”節點10”(數據為10的節點)，”節點10”的后繼節點是”節點20”(數據為10的節點)

3.1 單鏈表刪除節點

刪除”節點30”
刪除之前：”節點20” 的后繼節點為”節點30”，而”節點30” 的后繼節點為”節點40”。
刪除之后：”節點20” 的后繼節點為”節點40”。

3.2 單鏈表添加節點

在”節點10”與”節點20”之間添加”節點15”
添加之前：”節點10” 的后繼節點為”節點20”。
添加之后：”節點10” 的后繼節點為”節點15”，而”節點15” 的后繼節點為”節點20”。

單鏈表的特點是：節點的鏈接方向是單向的；相對于數組來說，單鏈表的的隨機訪問速度較慢，但是單鏈表刪除/添加數據的效率很高。

4. 雙向鏈表

雙向鏈表(雙鏈表)是鏈表的一種。和單鏈表一樣，雙鏈表也是由節點組成，它的每個數據結點中都有兩個指針，分別指向直接后繼和直接前驅。所以，從雙向鏈表中的任意一個結點開始，都可以很方便地訪問它的前驅結點和后繼結點。一般我們都構造雙向循環鏈表。

雙鏈表的示意圖如下：

表頭為空，表頭的后繼節點為”節點10”(數據為10的節點)；”節點10”的后繼節點是”節點20”(數據為10的節點)，”節點20”的前繼節點是”節點10”；”節點20”的后繼節點是”節點30”，”節點30”的前繼節點是”節點20”；…；末尾節點的后繼節點是表頭。

4.1 雙鏈表刪除節點

刪除”節點30”
刪除之前：”節點20”的后繼節點為”節點30”，”節點30” 的前繼節點為”節點20”。”節點30”的后繼節點為”節點40”，”節點40” 的前繼節點為”節點30”。
刪除之后：”節點20”的后繼節點為”節點40”，”節點40” 的前繼節點為”節點20”。

4.2 雙鏈表添加節點

在”節點10”與”節點20”之間添加”節點15”
添加之前：”節點10”的后繼節點為”節點20”，”節點20” 的前繼節點為”節點10”。
添加之后：”節點10”的后繼節點為”節點15”，”節點15” 的前繼節點為”節點10”。”節點15”的后繼節點為”節點20”，”節點20” 的前繼節點為”節點15”。

5. Java實現雙鏈表

/*** Java 實現的雙向鏈表。 * 注：java自帶的集合包中有實現雙向鏈表，路徑是:java.util.LinkedList** @author skywang* @date 2013/11/07*/ public class DoubleLink<T> {// 表頭private DNode<T> mHead;// 節點個數private int mCount;// 雙向鏈表“節點”對應的結構體private class DNode<T> {public DNode prev;public DNode next;public T value;public DNode(T value, DNode prev, DNode next) {this.value = value;this.prev = prev;this.next = next;}}// 構造函數public DoubleLink() {// 創建“表頭”。注意：表頭沒有存儲數據！mHead = new DNode<T>(null, null, null);mHead.prev = mHead.next = mHead;// 初始化“節點個數”為0mCount = 0;}// 返回節點數目public int size() {return mCount;}// 返回鏈表是否為空public boolean isEmpty() {return mCount==0;}// 獲取第index位置的節點private DNode<T> getNode(int index) {if (index<0 || index>=mCount)throw new IndexOutOfBoundsException();// 正向查找if (index <= mCount/2) {DNode<T> node = mHead.next;for (int i=0; i<index; i++)node = node.next;return node;}// 反向查找DNode<T> rnode = mHead.prev;int rindex = mCount - index -1;for (int j=0; j<rindex; j++)rnode = rnode.prev;return rnode;}// 獲取第index位置的節點的值public T get(int index) {return getNode(index).value;}// 獲取第1個節點的值public T getFirst() {return getNode(0).value;}// 獲取最后一個節點的值public T getLast() {return getNode(mCount-1).value;}// 將節點插入到第index位置之前public void insert(int index, T t) {if (index==0) {DNode<T> node = new DNode<T>(t, mHead, mHead.next);mHead.next.prev = node;mHead.next = node;mCount++;return ;}DNode<T> inode = getNode(index);DNode<T> tnode = new DNode<T>(t, inode.prev, inode);inode.prev.next = tnode;inode.next = tnode;mCount++;return ;}// 將節點插入第一個節點處。public void insertFirst(T t) {insert(0, t);}// 將節點追加到鏈表的末尾public void appendLast(T t) {DNode<T> node = new DNode<T>(t, mHead.prev, mHead);mHead.prev.next = node;mHead.prev = node;mCount++;}// 刪除index位置的節點public void del(int index) {DNode<T> inode = getNode(index);inode.prev.next = inode.next;inode.next.prev = inode.prev;inode = null;mCount--;}// 刪除第一個節點public void deleteFirst() {del(0);}// 刪除最后一個節點public void deleteLast() {del(mCount-1);} }

測試程序(DlinkTest.java)

/*** Java 實現的雙向鏈表。 * 注：java自帶的集合包中有實現雙向鏈表，路徑是:java.util.LinkedList** @author skywang* @date 2013/11/07*/public class DlinkTest {// 雙向鏈表操作int數據private static void int_test() {int[] iarr = {10, 20, 30, 40};System.out.println("\n----int_test----");// 創建雙向鏈表DoubleLink<Integer> dlink = new DoubleLink<Integer>();dlink.insert(0, 20); // 將 20 插入到第一個位置dlink.appendLast(10); // 將 10 追加到鏈表末尾dlink.insertFirst(30); // 將 30 插入到第一個位置// 雙向鏈表是否為空System.out.printf("isEmpty()=%b\n", dlink.isEmpty());// 雙向鏈表的大小System.out.printf("size()=%d\n", dlink.size());// 打印出全部的節點for (int i=0; i<dlink.size(); i++)System.out.println("dlink("+i+")="+ dlink.get(i));}private static void string_test() {String[] sarr = {"ten", "twenty", "thirty", "forty"};System.out.println("\n----string_test----");// 創建雙向鏈表DoubleLink<String> dlink = new DoubleLink<String>();dlink.insert(0, sarr[1]); // 將 sarr中第2個元素 插入到第一個位置dlink.appendLast(sarr[0]); // 將 sarr中第1個元素 追加到鏈表末尾dlink.insertFirst(sarr[2]); // 將 sarr中第3個元素 插入到第一個位置// 雙向鏈表是否為空System.out.printf("isEmpty()=%b\n", dlink.isEmpty());// 雙向鏈表的大小System.out.printf("size()=%d\n", dlink.size());// 打印出全部的節點for (int i=0; i<dlink.size(); i++)System.out.println("dlink("+i+")="+ dlink.get(i));}// 內部類private static class Student {private int id;private String name;public Student(int id, String name) {this.id = id;this.name = name;}@Overridepublic String toString() {return "["+id+", "+name+"]";}}private static Student[] students = new Student[]{new Student(10, "sky"),new Student(20, "jody"),new Student(30, "vic"),new Student(40, "dan"),};private static void object_test() {System.out.println("\n----object_test----");// 創建雙向鏈表DoubleLink<Student> dlink = new DoubleLink<Student>();dlink.insert(0, students[1]); // 將 students中第2個元素 插入到第一個位置dlink.appendLast(students[0]); // 將 students中第1個元素 追加到鏈表末尾dlink.insertFirst(students[2]); // 將 students中第3個元素 插入到第一個位置// 雙向鏈表是否為空System.out.printf("isEmpty()=%b\n", dlink.isEmpty());// 雙向鏈表的大小System.out.printf("size()=%d\n", dlink.size());// 打印出全部的節點for (int i=0; i<dlink.size(); i++) {System.out.println("dlink("+i+")="+ dlink.get(i));}}public static void main(String[] args) {int_test(); // 演示向雙向鏈表操作“int數據”。string_test(); // 演示向雙向鏈表操作“字符串數據”。object_test(); // 演示向雙向鏈表操作“對象”。} }

運行結果

----int_test---- isEmpty()=false size()=3 dlink(0)=30 dlink(1)=20 dlink(2)=10----string_test---- isEmpty()=false size()=3 dlink(0)=thirty dlink(1)=twenty dlink(2)=ten----object_test---- isEmpty()=false size()=3 dlink(0)=[30, vic] dlink(1)=[20, jody] dlink(2)=[10, sky]

6. 雙鏈表實現2

public class MyDoubleLink implements Iterable<Object>{private class Node{public Node(Object data){this.data = data;}Node next;Node prev;Object data;}private Node head;private Node rear;public void add(Object data){Node node = new Node(data);if (head == null){head = node;rear = node;} else {rear.next = node;node.prev = rear;rear = node;}}public boolean contains(Object data){Node node = find(data);return node != null;}public void print(){Node temp = head;while(temp != null){System.out.print(temp.data + ",");temp = temp.next;}System.out.println();}private Node find(Object data){Node node = head;while (node != null){if (node.data.equals(data) && node.data.hashCode() == data.hashCode()){break;} else {node = node.next;}}return node;}public void remove(Object data){Node node = find(data);if (node != null){if (node == head && node == rear){//只有一個節點head = null;rear = null;} else if (node == head){ //頭節點head = head.next;head.prev = null;} else if (node == rear){ //尾節點rear = rear.prev;rear.next = null;} else { //中間節點node.prev.next = node.next;node.next.prev = node.prev;}}}@Overridepublic Iterator<Object> iterator() {Iterator<Object> ite = new Iterator<Object>() {private Node temp = head;@Overridepublic boolean hasNext() {return temp != null;}@Overridepublic Object next() {// TODO Auto-generated method stubObject data = temp.data;temp = temp.next;return data;}@Overridepublic void remove() {// TODO Auto-generated method stub }};return ite;} }

6.1 測試雙鏈表

public class Test {public static class Instance{public Instance(int i){}public Instance(){}}public static void main(String[] args) {Instance in = new Instance(){};MyDoubleLink datas = new MyDoubleLink();datas.add("aaa");datas.add("bbb");datas.add("ccc");datas.print();datas.remove("ccc");datas.print();for (Object d : datas) {System.out.println(d);}} }

7. 雙鏈表

import java.util.Iterator; public class MyDoubleLink implements Iterable<Object>{private class Node{public Node(Object data){this.data = data;}Node next;Node prev;Object data;}private Node head;private Node rear;public void add(Object data){Node node = new Node(data);if (head == null){head = node;rear = node;} else {rear.next = node;node.prev = rear;rear = node;}}public boolean contains(Object data){Node node = find(data);return node != null;}public void print(){Node temp = head;while(temp != null){System.out.print(temp.data + ",");temp = temp.next;}System.out.println();}private Node find(Object data){Node node = head;while (node != null){if (node.data.equals(data) && node.data.hashCode() == data.hashCode()){break;} else {node = node.next;}}return node;}public void remove(Object data){Node node = find(data);if (node != null){if (node == head && node == rear){//只有一個節點head = null;rear = null;} else if (node == head){ //頭節點head = head.next;head.prev = null;} else if (node == rear){ //尾節點rear = rear.prev;rear.next = null;} else { //中間節點node.prev.next = node.next;node.next.prev = node.prev;}}}@Overridepublic Iterator<Object> iterator() {Iterator<Object> ite = new Iterator<Object>() {private Node temp = head;@Overridepublic boolean hasNext() {return temp != null;}@Overridepublic Object next() {// TODO Auto-generated method stubObject data = temp.data;temp = temp.next;return data;}@Overridepublic void remove() {// TODO Auto-generated method stub}};return ite;} } public class TEst {public static class Instance{public Instance(int i){}public Instance(){}}/*** @param args*/public static void main(String[] args) {// TODO Auto-generated method stubInstance in = new Instance(){};MyDoubleLink datas = new MyDoubleLink();datas.add("aaa");datas.add("bbb");datas.add("ccc");datas.print();datas.remove("ccc");datas.print();for (Object d : datas) {System.out.println(d);}} }

7.1 單鏈表的實現

// linkList2.java // demonstrates linked list // to run this program: C>java LinkList2App class Link{public int iData; // data item (key)public double dData; // data itempublic Link next; // next link in list // -------------------------------------------------------------public Link(int id, double dd) // constructor{iData = id;dData = dd;} // -------------------------------------------------------------public void displayLink() // display ourself{System.out.print("{" + iData + ", " + dData + "} ");}} // end class Link class LinkList{private Link first; // ref to first link on list// -------------------------------------------------------------public LinkList() // constructor{first = null; // no links on list yet} // -------------------------------------------------------------public void insertFirst(int id, double dd){ // make new linkLink newLink = new Link(id, dd);newLink.next = first; // it points to old first linkfirst = newLink; // now first points to this} // -------------------------------------------------------------public Link find(int key) // find link with given key{ // (assumes non-empty list)Link current = first; // start at 'first'while(current.iData != key) // while no match,{if(current.next == null) // if end of list,return null; // didn't find itelse // not end of list,current = current.next; // go to next link}return current; // found it} // -------------------------------------------------------------public Link delete(int key) // delete link with given key{ // (assumes non-empty list)Link current = first; // search for linkLink previous = first;while(current.iData != key){if(current.next == null)return null; // didn't find itelse{previous = current; // go to next linkcurrent = current.next;}} // found itif(current == first) // if first link,first = first.next; // change firstelse // otherwise,previous.next = current.next; // bypass itreturn current;} // -------------------------------------------------------------public void displayList() // display the list{System.out.print("List (first-->last): ");Link current = first; // start at beginning of listwhile(current != null) // until end of list,{current.displayLink(); // print datacurrent = current.next; // move to next link}System.out.println("");} // -------------------------------------------------------------} // end class LinkList class LinkList2App{public static void main(String[] args){LinkList theList = new LinkList(); // make listtheList.insertFirst(22, 2.99); // insert 4 itemstheList.insertFirst(44, 4.99);theList.insertFirst(66, 6.99);theList.insertFirst(88, 8.99);theList.displayList(); // display listLink f = theList.find(44); // find itemif( f != null)System.out.println("Found link with key " + f.iData);elseSystem.out.println("Can't find link");Link d = theList.delete(66); // delete itemif( d != null )System.out.println("Deleted link with key " + d.iData);elseSystem.out.println("Can't delete link");theList.displayList(); // display list} // end main()} // end class LinkList2App

7.2 有序鏈表

// sortedList.java // demonstrates sorted list // to run this program: C>java SortedListApp class Link{public long dData; // data itempublic Link next; // next link in list // -------------------------------------------------------------public Link(long dd) // constructor{ dData = dd; } // -------------------------------------------------------------public void displayLink() // display this link{ System.out.print(dData + " "); }} // end class Link class SortedList{private Link first; // ref to first item // -------------------------------------------------------------public SortedList() // constructor{ first = null; } // -------------------------------------------------------------public boolean isEmpty() // true if no links{ return (first==null); } // -------------------------------------------------------------public void insert(long key) // insert, in order{Link newLink = new Link(key); // make new linkLink previous = null; // start at firstLink current = first;// until end of list,while(current != null && key > current.dData){ // or key > current,previous = current;current = current.next; // go to next item}if(previous==null) // at beginning of listfirst = newLink; // first --> newLinkelse // not at beginningprevious.next = newLink; // old prev --> newLinknewLink.next = current; // newLink --> old currnt} // end insert() // -------------------------------------------------------------public Link remove() // return & delete first link{ // (assumes non-empty list)Link temp = first; // save firstfirst = first.next; // delete firstreturn temp; // return value} // -------------------------------------------------------------public void displayList(){System.out.print("List (first-->last): ");Link current = first; // start at beginning of listwhile(current != null) // until end of list,{current.displayLink(); // print datacurrent = current.next; // move to next link}System.out.println("");}} // end class SortedList class SortedListApp{public static void main(String[] args){ // create new listSortedList theSortedList = new SortedList();theSortedList.insert(20); // insert 2 itemstheSortedList.insert(40);theSortedList.displayList(); // display listtheSortedList.insert(10); // insert 3 more itemstheSortedList.insert(30);theSortedList.insert(50);theSortedList.displayList(); // display listtheSortedList.remove(); // remove an itemtheSortedList.displayList(); // display list} // end main()} // end class SortedListApp

7.3 雙向鏈表

// doublyLinked.java // demonstrates doubly-linked list // to run this program: C>java DoublyLinkedApp class Link{public long dData; // data itempublic Link next; // next link in listpublic Link previous; // previous link in list // -------------------------------------------------------------public Link(long d) // constructor{ dData = d; } // -------------------------------------------------------------public void displayLink() // display this link{ System.out.print(dData + " "); } // -------------------------------------------------------------} // end class Link class DoublyLinkedList{private Link first; // ref to first itemprivate Link last; // ref to last item // -------------------------------------------------------------public DoublyLinkedList() // constructor{first = null; // no items on list yetlast = null;} // -------------------------------------------------------------public boolean isEmpty() // true if no links{ return first==null; } // -------------------------------------------------------------public void insertFirst(long dd) // insert at front of list{Link newLink = new Link(dd); // make new linkif( isEmpty() ) // if empty list,last = newLink; // newLink <-- lastelsefirst.previous = newLink; // newLink <-- old firstnewLink.next = first; // newLink --> old firstfirst = newLink; // first --> newLink} // -------------------------------------------------------------public void insertLast(long dd) // insert at end of list{Link newLink = new Link(dd); // make new linkif( isEmpty() ) // if empty list,first = newLink; // first --> newLinkelse{last.next = newLink; // old last --> newLinknewLink.previous = last; // old last <-- newLink}last = newLink; // newLink <-- last} // -------------------------------------------------------------public Link deleteFirst() // delete first link{ // (assumes non-empty list)Link temp = first;if(first.next == null) // if only one itemlast = null; // null <-- lastelsefirst.next.previous = null; // null <-- old nextfirst = first.next; // first --> old nextreturn temp;} // -------------------------------------------------------------public Link deleteLast() // delete last link{ // (assumes non-empty list)Link temp = last;if(first.next == null) // if only one itemfirst = null; // first --> nullelselast.previous.next = null; // old previous --> nulllast = last.previous; // old previous <-- lastreturn temp;} // -------------------------------------------------------------// insert dd just after keypublic boolean insertAfter(long key, long dd){ // (assumes non-empty list)Link current = first; // start at beginningwhile(current.dData != key) // until match is found,{current = current.next; // move to next linkif(current == null)return false; // didn't find it}Link newLink = new Link(dd); // make new linkif(current==last) // if last link,{newLink.next = null; // newLink --> nulllast = newLink; // newLink <-- last}else // not last link,{newLink.next = current.next; // newLink --> old next// newLink <-- old nextcurrent.next.previous = newLink;}newLink.previous = current; // old current <-- newLinkcurrent.next = newLink; // old current --> newLinkreturn true; // found it, did insertion} // -------------------------------------------------------------public Link deleteKey(long key) // delete item w/ given key{ // (assumes non-empty list)Link current = first; // start at beginningwhile(current.dData != key) // until match is found,{current = current.next; // move to next linkif(current == null)return null; // didn't find it}if(current==first) // found it; first item?first = current.next; // first --> old nextelse // not first// old previous --> old nextcurrent.previous.next = current.next;if(current==last) // last item?last = current.previous; // old previous <-- lastelse // not last// old previous <-- old nextcurrent.next.previous = current.previous;return current; // return value} // -------------------------------------------------------------public void displayForward(){System.out.print("List (first-->last): ");Link current = first; // start at beginningwhile(current != null) // until end of list,{current.displayLink(); // display datacurrent = current.next; // move to next link}System.out.println("");} // -------------------------------------------------------------public void displayBackward(){System.out.print("List (last-->first): ");Link current = last; // start at endwhile(current != null) // until start of list,{current.displayLink(); // display datacurrent = current.previous; // move to previous link}System.out.println("");} // -------------------------------------------------------------} // end class DoublyLinkedList class DoublyLinkedApp{public static void main(String[] args){ // make a new listDoublyLinkedList theList = new DoublyLinkedList();theList.insertFirst(22); // insert at fronttheList.insertFirst(44);theList.insertFirst(66);theList.insertLast(11); // insert at reartheList.insertLast(33);theList.insertLast(55);theList.displayForward(); // display list forwardtheList.displayBackward(); // display list backwardtheList.deleteFirst(); // delete first itemtheList.deleteLast(); // delete last itemtheList.deleteKey(11); // delete item with key 11theList.displayForward(); // display list forwardtheList.insertAfter(22, 77); // insert 77 after 22theList.insertAfter(33, 88); // insert 88 after 33theList.displayForward(); // display list forward} // end main()} // end class DoublyLinkedApp

總結

以上是生活随笔為你收集整理的Java数据结构和算法：数组、单链表、双链表的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。