順序表示和鏈式表示的比較：
1.讀寫方式：順序表可以順序存取，也可以隨機存取；鏈表只能從表頭順序存取元素；
2.邏輯結構與物理結構：順序存儲時，邏輯上相鄰的元素其對應的物理存儲位置也相鄰；鏈式存儲時，邏輯上相鄰的元素，其物理存儲位置則不一定相鄰；
3.查找、插入和刪除操作：
按值查找，當線性表在無序的情況下，兩者的時間復雜度均為o(n)；而當順序表有序時，可采用折半查找，此時時間復雜度為o(log n)；
按位查找，順序表支持隨機訪問，時間復雜度為o(1)；而鏈表的平均時間復雜度為o(n)。
順序表的插入和刪除操作平均需要移動半個表長的元素；鏈表的插入、刪除操作時，只需修改相關節點的指針即可。
4.空間分配：順序存儲一般是基於靜態存儲分配，一單存儲空間裝滿就不能擴充；鏈式存儲的節點空間只有在需要的時候申請分配，只要內存有足夠的空間即可分配。
順序表示的實現：
public class ArrayList<E> {
final int defaultSize=0;
int maxSize; //線性表的最大長度
int length; //線性表當前長度
Object[] arrayList; //存儲線性表的數組
/*
* 構造函數
*/
public ArrayList(int size){
initList(size);
}
//按給定size初始化順序表
public void initList(int size) {
if(size < 0){
throw new RuntimeException("數組大小錯誤：" + size);
}else{
this.maxSize= size;
this.length=0;
this.arrayList = new Object[size];
}
}
//表長
public int length() {
return length;
}
//按值查找
public int locateElem(Object e) {
for(int i=0 ;i<length;i++){
if(arrayList[i] == e){
return i;
}
}
return -1;
}
//按位查找
public Object getElem(int i) {
if(i<0 || i>=length ){
throw new RuntimeException("參數出錯："+i);
}
if(length ==0){
throw new RuntimeException("順序表為空");
}
return arrayList[i];
}
//插入
public void insert(int i, Object e) {
if(i<0 || i>length+1 ){
throw new RuntimeException("新元素插入位置有誤："+i);
}
if(i >= maxSize){
throw new RuntimeException("順序表已滿，不能再插入新的元素");
}
for(int j=length;j<i; j--){
arrayList[j]=arrayList[j-1];
}
arrayList[i]=e;
length++;
}
//刪除
public void delete(int i, Object e) {
if(i<0 || i > length-1){
throw new RuntimeException("需刪除元素位置有誤："+i);
}
if(length == 0){
throw new RuntimeException("順序表為空，不能刪除元素");
}
for(int j=i;j<length-1;j++){
arrayList[j] = arrayList[j+1];
}
arrayList[length-1]="";
length--;
}
//判空
public boolean isEmpty() {
return length==0 ? true : false;
}
//刪除順序表
public void destroyList() {
this.arrayList=null;
this.length=0;
this.maxSize=0;
}
}
單鏈表表示的實現：
class Node<E>{
E e; //數據
Node<E> next; //下一個節點
Node(){}
Node(E e){
this.e = e;
this.next = null;
}
}
public class LinkedList<E> {
private Node<E> header = null; //頭結點
int size=0; //鏈表大小
public LinkedList() {
this.header = new Node<E>();
}
//得到鏈表的長度
public int length() {
return size;
}
//按值查找節點，返回該節點的位置
public int locateElem(E e) {
Node<E> temp = header;
int count = 1;
while(temp.next != null && temp.e != e){
temp = temp.next;
count ++;
}
return count;
}
//找到第index個位置的節點
public Node<E> getNode(int index) {
if(index > size || index < 0){
throw new RuntimeException("索引值有錯：" + index);
}
Node<E> temp = new Node<E>();
temp = header;
int count=1;
while(count != index){
temp = temp.next;
count ++;
}
return temp;
}
//尾添加
public boolean addToLast(E e) {
if(size == 0){
header.e = e;
}else{
Node<E> newnode = new Node<E>(e); //根據需要添加的內容封裝為節點
Node<E> last = getNode(size); //得到最後一個節點
last.next = newnode;
}
size ++;
return true;
}
//頭添加
public boolean addTofirst(E e) {
if(size == 0){
header.e = e;
}else{
Node<E> newnode = new Node<E>(e); //根據需要添加的內容封裝為節點
newnode.next = header.next;
header.next = newnode;
}
size ++;
return true;
}
//插入到第index個的位置
public boolean insert(int index, E e) {
Node<E> newnode = new Node<E>(e); //根據需要添加的內容封裝為節點
Node<E> cnode = getNode(index-1); //得到第index-1個節點
newnode.next = cnode.next;
cnode.next = newnode;
size++;
return true;
}
//刪除第index個節點
public boolean delete(int index) {
Node<E> prinode = getNode(index-1); //得到被刪除的節點的前一個節點
Node<E> delnode = prinode.next; //得到被刪除的節點
prinode.next = delnode.next;
size --;
return true;
}
//判空
public boolean isEmpty() {
return size==0 ? true : false;
}
public void destroyList() {
header = null;
size = 0;
}
//輸出
public String toString(){
StringBuilder s = new StringBuilder("[");
Node<E> temp = header;
for(int i=0; i < size;i++){
s.append(temp.e.toString()+" ");
temp = temp.next;
}
s.append("]");
return s.toString();
}
}
雙鏈表表示的實現
class TNode<E>{
E e;
TNode<E> prior, next;
TNode(){}
TNode(E e){
this.e = e;
prior = null;
next = null;
}
}
public class DoubleLinkedList<E> {
private TNode<E> header = null; //頭結點
int size=0; //鏈表大小
public DoubleLinkedList(){
this.header = new TNode<E>();
}
//尾添加
public boolean addToLast(E e) {
if(size == 0){
header.e = e;
}else{
TNode<E> TNode = new TNode<E>(e); //根據需要添加的內容封裝為節點
TNode<E> last = getNode(size); //得到最後一個節點
last.next = TNode;
TNode.prior=last;
}
size ++;
return true;
}
//找到第index個位置的節點
public TNode<E> getNode(int index){
if(index > size || index < 0){
throw new RuntimeException("索引值有錯：" + index);
}
TNode<E> temp = new TNode<E>();
temp = header;
int count =1;
while(count != index){
temp = temp.next;
count ++;
}
return temp;
}
//插入到第index個的位置
public boolean insert(int index,E e){
TNode<E> TNode = new TNode<E>(e);
TNode<E> cnode = getNode(index-1); //找到第index-1個位置的節點
TNode.next=cnode.next;
TNode.prior = cnode;
cnode.next.prior = TNode;
cnode.next = TNode;
size++;
return true;
}
//刪除第index個節點
public boolean delete(int index){
TNode<E> delnode = getNode(index);
delnode.prior.next=delnode.next;
delnode.next.prior= delnode.prior;
size--;
return true;
}
}
