線性表概述

線性表是最基本、最簡單、也是最常用的一種資料結構。線上性表中資料元素之間的關系是線性，資料元素可以看成是排列在一條線上或一個環上。

線性表分為靜态線性表和動态線性表，常見的有順序表(靜态的)、單向連結清單(動态的)和雙向連結清單(動态的)。

線性表的操作主要包括：

（1）計算表的長度n。

（2）線性表是否為空

（3）将元素添加到線性表的末尾

（4）擷取第i個元素，0≤i < n。

（5）清除線性表

（6）傳回清單中首次出現指定元素的索引，如果清單不包含此元素，則傳回 -1。

（7）傳回清單中最後一次出現指定元素的索引，如果清單不包含此元素，則傳回 -1。

（8）将新元素插入第i個位置，0≤i < n，使原來的第i，i+1，…，n–1個元素變為第i+1，i+2，…，n個元素。

（9）更改第i個元素

（10）删除第i個元素，0≤i < n，使原來的第i+1，i+2，…，n–1個元素變為第i，i+1，…，n–2個元素

由此，對線性表抽象資料類型定義List接口如下：

List接口

package list;

public interface List {
	/**
	 * 将元素添加到線性表的末尾
	 */
	public void add(Object e);
	
	/**
	 * 清除線性表
	 */
	public void clear();
	/**
	 * 擷取i位置的元素
	 * @param i
	 * @return
	 */
	public Object get(int i);
	/**
	 * 傳回清單中首次出現指定元素的索引，如果清單不包含此元素，則傳回 -1。
	 * @param e
	 * @return
	 */
	public int indexOf(Object e);
	/**
	 * 在i後面插入一個元素e
	 * @param i
	 * @param e
	 */
	public void insert(int i, Object e);
	/**
	 * 判斷線性表是否為空
	 * @return
	 */
	public boolean isEmpty();
	/**
	 * 回清單中最後出現指定元素的索引，如果清單不包含此元素，則傳回 -1。
	 * @param e
	 * @return
	 */
	public int lastIndexOf(Object e);
	/**
	 *  移除清單中指定位置的元素
	 * @param i
	 */
	public void remove(int i);
	/**
	 * 用指定元素替換清單中指定位置的元素（可選操作）。
	 * @param i
	 * @param e
	 */
	public void set(int i, Object e);
	/**
	 * 傳回線性表的大小
	 * @return
	 */
	public int size();
}

順序表

結構模型

線性表線性表概述順序表單向循環連結清單雙向循環連結清單測試線性表

圖順序存儲結構記憶體結構示意圖

源代碼

package list;

public class ArrayList implements List{
	/**
	 * 順序表預設的初始大小
	 */
	public static final int defLen = 10;
	private int maxLen;
	private Object[] array;
	private int size;
	
	public ArrayList() {
		size = 0;
		maxLen = defLen;
		array = new Object[defLen];
	}
	
	@Override
	public void clear() {
		size = 0;
	}

	@Override
	public Object get(int i) {
		if(i>=0 && i<size)
			return array[i];
		else
			return null;
	}

	@Override
	public int indexOf(Object e) {
		int i =0; 
		while(i<size && !array[i].equals(e)) {
			i++;
		}
		if(i < size)
			return i;
		else
			return -1;
	}

	@Override
	public void insert(int i, Object e) {
		if(i >= size) {
			i = size;
			if((size) >= maxLen)//如果插入數的位置大于順序表的最大容量，則擴大容量
				expand();
		}
		for(int j = size; j>i+1; j--) {
			array[j] = array[j-1];
		}
		array[i+1] = e;
		size ++;
	}

	@Override
	public boolean isEmpty() {
		if(size == 0)
			return true;
		else 
			return false;
	}

	@Override
	public int lastIndexOf(Object e) {
		int i = size-1;
		while(i>=0 && !array[i].equals(e)) {
			i--;
		}
		if(i>=0)
			return i;
		else
			return -1;
	}

	@Override
	public void remove(int i) {
		for(int j=i; j<size-1; j++) {
			array[j] = array[j+1];
		}
		size --;
	}

	@Override
	public void set(int i, Object e) {
		array[i] = e;
	}

	@Override
	public int size() {
		return size;
	}
	/**
	 * 當順序表的大小不夠時，擴充順序表的大小
	 */
	private void expand() {
		maxLen = 2*maxLen;
		Object newArray[] = new Object[maxLen];
		for(int i=0; i<size; i++) {
			newArray[i] = array[i];
		}
		array = newArray;
	}

	@Override
	public void add(Object e) {
		if(size >=maxLen)
			expand();
		array[size] = e;
		size ++;
	}
}

單向循環連結清單

結構模型

線性表線性表概述順序表單向循環連結清單雙向循環連結清單測試線性表

帶頭結點的單鍊結構

(a)空鍊； (b)非空鍊

源代碼

package list;
/**
 * 連結清單的結點
 * @author luoweifu
 *
 */
class Node{
	Object data;	//資料元素
	Node next;		//後驅結點
	public Node() {
		this(null);
	}
	public Node(Object data) {
		this.data = data;
		this.next = null;
	}
}
/**
 * 帶頭結點的鍊式連結清單,下标從0開始; 
 * @author Administrator
 *
 */
public class LinkList implements List {
	Node head;	//頭結點
	int size;	//連結清單的大小
	public LinkList() {
		head = new Node();
		size = 0;
	}
	public LinkList(Object[] datas) {
		int n = datas.length;
		head = new Node();
		Node p = head;
		for(int i=0; i<n; i++) {
			p.next = new Node(datas[i]);
			p = p.next;
		}
		size = n;
	}
	@Override
	public void add(Object e) {
		Node p;
		if(0 == size) {
			p = head;
		} else {
			p = index(size-1);
		}
		p.next = new Node(e);
		size ++;
	}

	@Override
	public void clear() {
		head.next = null;
		size = 0;
	}

	@Override
	public Object get(int i) {
		Node p = index(i);
		return p.data;
	}
	
	private Node index(int i) {
		Node p = null;
		if(i>=0 && i<size){
			p = head;
			for(int j=0; j<=i; j++) {
				p = p.next;
			}
		} 
		return p;
	}

	@Override
	public int indexOf(Object e) {
		Node p = head.next;
		int i = 0;
		while(!p.data.equals(e)) {
			p = p.next;
			i++;
		}
		if(i<size)
			return i;
		else 
			return -1;
	}

	@Override
	public void insert(int i, Object e) {
		Node p = index(i);
		Node p2 = new Node(e);
		p2.next = p.next;
		p.next = p2;
		size ++;
	}

	@Override
	public boolean isEmpty() {
		if(size ==0)
			return true;
		else
			return false;
	}

	@Override
	public int lastIndexOf(Object e) {
		int i = size-1;
		while(!get(i).equals(e)) {
			i--;
		}
		if(i>=0)
			return i;
		else 
			return -1;
	}

	@Override
	public void remove(int i) {
		if(i>=0 && i<size) {
			Node p = null;
			if(i == 0)
				p = head;
			else {
				p = index(i-1);
			}
			p.next = index(i).next;
		}
		size --;
	}

	@Override
	public void set(int i, Object e) {
		Node p = index(i);
		p.data = e;
	}

	@Override
	public int size() {
		return size; 
	}
	
}

雙向循環連結清單

結構模型

線性表線性表概述順序表單向循環連結清單雙向循環連結清單測試線性表

帶頭結點的雙循環鍊結構

(a)空鍊； (b)非空鍊

源代碼

package list;
/**
 * 連結清單的結點
 * @author luoweifu
 *
 */
class DlNode{
	Object data;
	DlNode prior, next;
	public DlNode() {
		this(null);
	}
	public DlNode(Object data) {
		this.data = data;	//資料元素
		this.prior = null;	//前驅結點
		this.next = null;	//後驅結點
	}
}
/**
 * 帶頭結點的雙向循環連結清單,下标從0開始; 
 * @author Administrator
 *
 */
public class DoubleLinkList implements List {
	DlNode head;	//頭結點
	int size;	//連結清單的大小
	public DoubleLinkList() {
		head = new DlNode();
		head.prior = head;
		head.next = head;
		size = 0;
	}
	public DoubleLinkList(Object[] datas) {
		int n = datas.length;
		head = new DlNode();
		DlNode p = head;
		DlNode p2 = null;
		for(int i=0; i<n; i++) {
			p2 = new DlNode(datas[i]);
			p.next = p2;
			p2.prior = p;
			p = p.next;
		}
		p2.next = head;
		head.prior = p2; 
		size = n;
	}
	@Override
	public void add(Object e) {
		DlNode p, p2;
		if(0 == size) {
			p = head;
		} else {
			p = index(size-1);
		}
		p2 = new DlNode(e);
		p.next = p2;
		p2.prior = p;
		p2.next = head;
		head.prior = p2;
		size ++;
	}

	@Override
	public void clear() {
		head.prior = head;
		head.next = head;
		size = 0;
	}

	@Override
	public Object get(int i) {
		DlNode p = index(i);
		return p.data;
	}
	
	private DlNode index(int i) {
		DlNode p = null;
		if(i>=0 && i<size){
			p = head;
			for(int j=0; j<=i; j++) {
				p = p.next;
			}
		} 
		return p;
	}

	@Override
	public int indexOf(Object e) {
		DlNode p = head.next;
		int i = 0;
		while(!p.data.equals(e)) {
			p = p.next;
			i++;
		}
		if(i<size)
			return i;
		else 
			return -1;
	}

	@Override
	public void insert(int i, Object e) {
		DlNode p = index(i);
		DlNode p2 = new DlNode(e);
		p2.next = p.next;
		p2.prior = p;
		p.next = p2;
		size ++;
	}

	@Override
	public boolean isEmpty() {
		if(size ==0)
			return true;
		else
			return false;
	}

	@Override
	public int lastIndexOf(Object e) {
		DlNode p = head.prior;
		int i = size-1;
		while(!p.data.equals(e)) {
			p = p.prior;
			i--;
		}
		if(i>=0)
			return i;
		else 
			return -1;
	}

	@Override
	public void remove(int i) {
		if(i>=0 && i<size) {
			DlNode p = null;
			if(i == 0)
				p = head;
			else {
				p = index(i-1);
			}
			DlNode p2 = index(i).next;
			p.next = p2.next;
			p2.next.prior = p;
		}
		size --;
	}

	@Override
	public void set(int i, Object e) {
		DlNode p = index(i);
		p.data = e;
	}

	@Override
	public int size() {
		return size; 
	}
	
}

測試線性表

package list;

public class Test {

	/**
	 * 測試線性表
	 * @param args
	 */
	public static void main(String args[]) {
		List list = new ArrayList();
		//List list = new LinkList();
		//List list = new DoubleLinkList();
		for(int i=0; i<10; i++) {
			list.add(new Integer(i));
		}
		list.remove(9);
		System.out.print("size;" + list.size() + "\n");
		System.out.println("isEmpty:" + list.isEmpty());
		System.out.print("第7個位置的元素：" + list.get(7) + "\n");	
		for(int i=0; i<list.size(); i++) {
			System.out.print(list.get(i) + "    ");
		}
		
		list.add(21);
		list.add(22);
		list.insert(3, new Integer(5));
		System.out.print("size:" + list.size() + "\n");
		System.out.print("第一次出現5的索引：" + list.indexOf(5) + "\n");
		System.out.print("最後一次出現5的索引：" + list.lastIndexOf(5) + "\n");
		list.set(0, new Integer(30));
		for(int i=0; i<list.size(); i++) {
			System.out.print(list.get(i) + "    ");
		}
	}
}

結果

size;9

isEmpty:false

第7個位置的元素：7

0 1 2 3 4 5 6 7 8 size:12

第一次出現5的索引：4

最後一次出現5的索引：6

30 1 2 3 5 4 5 6 7 8 21 22

線性表線性表概述順序表單向循環連結清單雙向循環連結清單測試線性表

線性表概述

List接口

順序表

結構模型

源代碼

單向循環連結清單

結構模型

源代碼

雙向循環連結清單

結構模型

源代碼

測試線性表

結果

繼續閱讀

樹的基本概念(定義、基本術語、性質)

GSL--GNU Scientific Library

D5|哈希表，善用資料結構

如何成為一名.net 工程師?

BMP檔案結構及圖像每行位元組計算方法

D. Ehab the Xorcist(構造+思維)

查找算法之二分查找查找算法之二分查找

JAVA高效程式設計指南

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

【資料結構】醫院選址

[轉]ISUP信令的IAM消息詳細内容

筆試面試題目：滑動視窗(二)

交通/城市相關的公開的資料集上學時整理的Xie et al., 2020收集的

資料結構與算法（27）——排序（二）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

Linux裝置模型（中）之上層容器