Java面試寶典之?dāng)?shù)據(jù)結(jié)構(gòu)基礎(chǔ) —— 線性表篇
作者：egg
郵箱：xtfggef@gmail.com
微博：http://weibo.com/xtfggef
博客：http://blog.csdn.net/zhangerqing（轉(zhuǎn)載請說明出處）
這部分內(nèi)容作為計(jì)算機(jī)專業(yè)最基礎(chǔ)的知識(shí)，幾乎被所有企業(yè)選中用來作考題，因此，本章我們從本章開始，我們將從基礎(chǔ)方面對數(shù)據(jù)結(jié)構(gòu)進(jìn)行講解，內(nèi)容主要是線性表，包括棧、隊(duì)列、數(shù)組、字符串等，主要講解基礎(chǔ)知識(shí)，如概念及簡單的實(shí)現(xiàn)代碼，非線性結(jié)構(gòu)我們在后面的文章中給出。過程中有任
何問題，請聯(lián)系本人：http://weibo.com/xtfggef?
一、數(shù)據(jù)結(jié)構(gòu)概念
用我的理解，數(shù)據(jù)結(jié)構(gòu)包含數(shù)據(jù)和結(jié)構(gòu)，通俗一點(diǎn)就是將數(shù)據(jù)按照一定的結(jié)構(gòu)組合起來，不同的組合方式會(huì)有不同的效率，使用不同的場景，如此而已。比如我們最常用的數(shù)組，就是一種數(shù)據(jù)結(jié)構(gòu)，有獨(dú)特的承載數(shù)據(jù)的方式，按順序排列，其特點(diǎn)就是你可以根據(jù)下標(biāo)快速查找元素，但是因?yàn)樵跀?shù)組中插入和刪除元素會(huì)有其它元素較大幅度的便宜，所以會(huì)帶來較多的消耗，所以因?yàn)檫@種特點(diǎn)，使得數(shù)組適合：查詢比較頻繁，增、刪比較少的情況，這就是數(shù)據(jù)結(jié)構(gòu)的概念。數(shù)據(jù)結(jié)構(gòu)包括兩大類：線性結(jié)構(gòu)和非線性結(jié)構(gòu)，線性結(jié)構(gòu)包括：數(shù)組、鏈表、隊(duì)列、棧等，非線性結(jié)構(gòu)包括樹、圖、表等及衍生類結(jié)構(gòu)。本章我們先講解線性結(jié)構(gòu)，主要從數(shù)組、鏈表、隊(duì)列、棧方面進(jìn)行討論，非線性數(shù)據(jù)結(jié)構(gòu)在后面會(huì)繼續(xù)講解。
二、線性表
線性表是最基本、最簡單、也是最常用的一種數(shù)據(jù)結(jié)構(gòu)。線性表中數(shù)據(jù)元素之間的關(guān)系是一對一的關(guān)系，即除了第一個(gè)和最后一個(gè)數(shù)據(jù)元素之外，其它數(shù)據(jù)元素都是首尾相接的。線性表的邏輯結(jié)構(gòu)簡單，便于實(shí)現(xiàn)和操作。因此，線性表這種數(shù)據(jù)結(jié)構(gòu)在實(shí)際應(yīng)用中是廣泛采用的一種數(shù)據(jù)結(jié)構(gòu)。其基本操作主要有：
? ?1）MakeEmpty(L) 這是一個(gè)將L變?yōu)榭毡淼姆椒?br />? ?2）Length（L） 返回表L的長度，即表中元素個(gè)數(shù)?
不管采用哪種方式實(shí)現(xiàn)線性表，至少都應(yīng)該具有上述這些基本方法，下面我會(huì)將下數(shù)據(jù)結(jié)構(gòu)的基本實(shí)現(xiàn)方式。
三、基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)
數(shù)據(jù)結(jié)構(gòu)是一種抽象的數(shù)據(jù)類型（ADT），可以這么說，我們可以采用任意的方式實(shí)現(xiàn)某種數(shù)據(jù)結(jié)構(gòu)，只要符合將要實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)，數(shù)據(jù)結(jié)構(gòu)就是一種標(biāo)準(zhǔn)，我們可以采用不同的方式去實(shí)現(xiàn)，最常用的兩種就是數(shù)組和鏈表（包括單鏈表、雙向鏈表等）。數(shù)組是非常常見的數(shù)據(jù)類型，在任何一種語言里都有它的實(shí)現(xiàn)，我們這里采用Java來簡單實(shí)現(xiàn)一下數(shù)組。
int a[]; int [] b; int []c;
a =
new int [
10 ];
總結(jié)起來，聲明一個(gè)數(shù)組有基本的三個(gè)因素：類型、名稱、下標(biāo)，Java里，數(shù)組在格式上相對靈活，下標(biāo)和名稱可以互換位置，前三種情況我們可以理解為聲明一個(gè)變量，后一種為其賦值?；蛘呦裣旅孢@樣，在聲明的時(shí)候賦值：
int c[] = {2 ,3 ,6 ,10 ,99 }; int []d = new int [10 ];
我稍微解釋一下，其實(shí)如果只執(zhí)行：int[] b,只是在棧上創(chuàng)建一個(gè)引用變量，并未賦值，只有當(dāng)執(zhí)行d = new int[10]才會(huì)在堆上真正的分配空間。上述第一行為靜態(tài)初始化，就是說用戶指定數(shù)組的內(nèi)容，有系統(tǒng)計(jì)算數(shù)組的大小，第二行恰恰相反，用戶指定數(shù)組的大小，由系統(tǒng)分配初始值，我們打印一下數(shù)組的初始值：
int []d = new int [10 ]; System.out.println(d[2 ]); 結(jié)果輸出0，對于int類型的數(shù)組，默認(rèn)的初始值為0.
但是，絕對不可以像下面這樣：
int e[
10 ] =
new int [
10 ];無法通過編譯，至于為什么，語法就是這樣，這是一種規(guī)范，不用去想它。
我們可以通過下標(biāo)來檢索數(shù)組。下面我舉個(gè)簡單的例子，來說明下數(shù)組的用法。
public static void main (String[] args) String name[]; name = new String[5 ]; name[0 ] = "egg" ; name[1 ] = "erqing" ; name[2 ] = "baby" ; for (int i = 0 ; i < name.length; i++) { System.out.println(name[i]); } } 這是最簡單的數(shù)組聲明、創(chuàng)建、賦值、遍歷的例子，下面寫個(gè)增刪的例子。
package com.xtfggef.algo.array; public class Array public static void main (String[] args) int value[] = new int [10 ]; for (int i = 0 ; i < 10 ; i++) { value[i] = i; } delete(value, 3 ); traverse(value); } public static int [] insert(int [] old, int value, int index) { for (int k = old.length - 1 ; k > index; k--) old[k] = old[k - 1 ]; old[index] = value; return old; } public static void traverse (int data[]) for (int j = 0 ; j < data.length; j++) System.out.print(data[j] + " " ); } public static int [] delete(int [] old, int index) { for (int h = index; h < old.length - 1 ; h++) { old[h] = old[h + 1 ]; } old[old.length - 1 ] = 0 ; return old; } } 簡單寫一下，主要想說明數(shù)組中刪除和增加元素的原理：增加元素，需要將index后面的依次向后移動(dòng)，然后將值插入index位置，刪除則將后面的值依次向前移動(dòng)，較簡單。
要記住：數(shù)組是表示相同類型的一類數(shù)據(jù)的集合，下標(biāo)從0開始，就行了。
數(shù)組實(shí)現(xiàn)的線下表可以參考ArrayList，在JDK中附有源碼，感興趣的同學(xué)可以讀讀。下面我簡單介紹下單鏈表。
單鏈表是最簡單的鏈表，有節(jié)點(diǎn)之間首尾連接而成，簡單示意如下：
除了頭節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)包含一個(gè)數(shù)據(jù)域一個(gè)指針域，除了頭、尾節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)的指針指向下一個(gè)節(jié)點(diǎn)，下面我們寫個(gè)例子操作一下單鏈表。
package com.xtfggef.algo.linkedlist; public class LinkedList <T > private static class Node <T > T data; Node<T> next; Node(T data, Node<T> next) { this .data = data; this .next = next; } Node(T data) { this (data, null ); } } private Node<T> head, tail; public LinkedList () head = tail = null ; } public boolean isEmpty () return head == null ; } public void addHead (T item) head = new Node<T>(item); if (tail == null ) tail = head; } public void addTail (T item) if (!isEmpty()) { tail.next = new Node<T>(item); tail = tail.next; } else { head = tail = new Node<T>(item); } } public void traverse () if (isEmpty()) { System.out.println("null" ); } else { for (Node<T> p = head; p != null ; p = p.next) System.out.println(p.data); } } public void addFromHead (T item) Node<T> newNode = new Node<T>(item); newNode.next = head; head = newNode; } public void addFromTail (T item) Node<T> newNode = new Node<T>(item); Node<T> p = head; while (p.next != null ) p = p.next; p.next = newNode; newNode.next = null ; } public void removeFromHead () if (!isEmpty()) head = head.next; else System.out.println("The list have been emptied!" ); } public void removeFromTail () Node<T> prev = null , curr = head; while (curr.next != null ) { prev = curr; curr = curr.next; if (curr.next == null ) prev.next = null ; } } public boolean insert (T appointedItem, T item) Node<T> prev = head, curr = head.next, newNode; newNode = new Node<T>(item); if (!isEmpty()) { while ((curr != null ) && (!appointedItem.equals(curr.data))) { prev = curr; curr = curr.next; } newNode.next = curr; prev.next = newNode; return true ; } return false ; } public void remove (T item) Node<T> curr = head, prev = null ; boolean found = false ; while (curr != null && !found) { if (item.equals(curr.data)) { if (prev == null ) removeFromHead(); else prev.next = curr.next; found = true ; } else { prev = curr; curr = curr.next; } } } public int indexOf (T item) int index = 0 ; Node<T> p; for (p = head; p != null ; p = p.next) { if (item.equals(p.data)) return index; index++; } return -1 ; } public boolean contains (T item) return indexOf(item) != -1 ; } } 單鏈表最好玩兒的也就是增加和刪除節(jié)點(diǎn)，下面的兩個(gè)圖分別是用圖來表示單鏈表增、刪節(jié)點(diǎn)示意，看著圖學(xué)習(xí)，理解起來更加容易！
接下來的隊(duì)列和棧，我們分別用不同的結(jié)構(gòu)來實(shí)現(xiàn)，隊(duì)列用數(shù)組，棧用單列表，讀者朋友對此感興趣，可以分別再用不同的方法實(shí)現(xiàn)。
package com.xtfggef.algo.queue; import java.util.Arrays; public class Queue <T > private int DEFAULT_SIZE = 10 ; private int capacity; private Object[] elementData; private int front = 0 ; private int rear = 0 ; public Queue () { capacity = DEFAULT_SIZE; elementData = new Object[capacity]; } public Queue (T element) { this (); elementData[0 ] = element; rear++; } public Queue (T element , int initSize) { this .capacity = initSize; elementData = new Object[capacity]; elementData[0 ] = element; rear++; } public int size () { return rear - front; } public void add (T element) { if (rear > capacity - 1 ) { throw new IndexOutOfBoundsException("the queue is full!" ); } elementData[rear++] = element; } public T remove () { if (empty()) { throw new IndexOutOfBoundsException("queue is empty" ); } @SuppressWarnings ("unchecked" ) T oldValue = (T)elementData[front]; elementData[front++] = null ; return oldValue; } @SuppressWarnings ("unchecked" ) public T element () { if (empty()) { throw new IndexOutOfBoundsException("queue is empty" ); } return (T)elementData[front]; } public boolean empty () { return rear == front; } public void clear () { Arrays.fill(elementData , null ); front = 0 ; rear = 0 ; } public String toString () { if (empty()) { return "[]" ; } else { StringBuilder sb = new StringBuilder("[" ); for (int i = front ; i < rear ; i++ ) { sb.append(elementData[i].toString() + ", " ); } int len = sb.length(); return sb.delete(len - 2 , len).append("]" ).toString(); } } public static void main (String[] args) Queue<String> queue = new Queue<String>("ABC" , 20 ); queue.add("DEF" ); queue.add("egg" ); System.out.println(queue.empty()); System.out.println(queue.size()); System.out.println(queue.element()); queue.clear(); System.out.println(queue.empty()); System.out.println(queue.size()); } } 隊(duì)列只能在表頭進(jìn)行刪除，在表尾進(jìn)行增加，這種結(jié)構(gòu)的特點(diǎn)，適用于排隊(duì)系統(tǒng)。
五、棧
棧是一種后進(jìn)先出（Last In First Out，LIFO）的數(shù)據(jù)結(jié)構(gòu)，我們采用單鏈表實(shí)現(xiàn)一個(gè)棧。
package com.xtfggef.algo.stack; import com.xtfggef.algo.linkedlist.LinkedList; public class Stack <T > static class Node <T > T data; Node<T> next; Node(T data, Node<T> next) { this .data = data; this .next = next; } Node(T data) { this (data, null ); } } @SuppressWarnings ("rawtypes" ) static LinkedList list = new LinkedList(); @SuppressWarnings ("unchecked" ) public T push (T item) list.addFromHead(item); return item; } public void pop () list.removeFromHead(); } public boolean empty () return list.isEmpty(); } public int search (T t) return list.indexOf(t); } public static void main (String[] args) Stack<String> stack = new Stack<String>(); System.out.println(stack.empty()); stack.push("abc" ); stack.push("def" ); stack.push("egg" ); stack.pop(); System.out.println(stack.search("def" )); } } 本章的內(nèi)容都是很基礎(chǔ)的，重在讓讀者朋友們理解數(shù)據(jù)結(jié)構(gòu)的概念，下章開始，我們會(huì)介紹樹、二叉樹等Java中的實(shí)現(xiàn)，敬請讀者朋友們持續(xù)關(guān)注！
作者：egg
郵箱：xtfggef@gmail.com
微博：http://weibo.com/xtfggef
博客：http://blog.csdn.net/zhangerqing（轉(zhuǎn)載請說明出處）
有問題，請依照上述聯(lián)系方式聯(lián)系作者，歡迎讀者及時(shí)提出建議，謝謝！
與50位技術(shù)專家面對面 20年技術(shù)見證，附贈(zèng)技術(shù)全景圖
總結(jié)
以上是生活随笔 為你收集整理的Java面试宝典系列之基础面试题String、变量、类与对象、集合类、SSH(三) 的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔 網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔 推薦給好友。
