鏈表結(jié)構(gòu)
鏈?zhǔn)酱鎯Y(jié)構(gòu)是基于指針實(shí)現(xiàn)的。我們把一個數(shù)據(jù)元素和一個指針稱為結(jié)點(diǎn)。鏈?zhǔn)酱鎯Y(jié)構(gòu)是用指針把相互直接關(guān)聯(lián)的結(jié)點(diǎn)（即直接前驅(qū)結(jié)點(diǎn)或直接后繼結(jié)點(diǎn)）鏈接起來币励。鏈?zhǔn)酱鎯Y(jié)構(gòu)的線性表稱為鏈表
鏈表類型
根據(jù)鏈表的構(gòu)造方式的不同可以分為：
- 單向鏈表
- 單向循環(huán)鏈表
- 雙向循環(huán)鏈表
單鏈表
單鏈表是構(gòu)成鏈表的每個結(jié)點(diǎn)只有一個指向直接后繼結(jié)點(diǎn)的指針阳仔。單鏈表的表示方法，單鏈表中每個結(jié)點(diǎn)的結(jié)構(gòu)：
單鏈表結(jié)構(gòu)
單鏈表有帶頭結(jié)點(diǎn)結(jié)構(gòu)和不帶頭結(jié)點(diǎn)結(jié)構(gòu)兩種导俘。我們把指向單鏈表的指針稱為單鏈表的頭指針甘磨。頭指針?biāo)傅牟淮娣艛?shù)據(jù)元素的第一個結(jié)點(diǎn)稱作頭結(jié)點(diǎn)强法。存放第一個數(shù)據(jù)元素的結(jié)點(diǎn)稱作第一個數(shù)據(jù)元素結(jié)點(diǎn)，或稱首元結(jié)點(diǎn)。
節(jié)點(diǎn)類
單鏈表是由一個一個結(jié)點(diǎn)組成的荆陆，因此，要設(shè)計單鏈表類饼问，必須先設(shè)計結(jié)點(diǎn)類稚照。結(jié)點(diǎn)類的成員變量有兩個：一個是數(shù)據(jù)元素，另一個是表示下一個結(jié)點(diǎn)的對象引用（即指針）凯沪。設(shè)計操作
- 頭結(jié)點(diǎn)的初始化
- 非頭結(jié)點(diǎn)的構(gòu)造
- 獲取該結(jié)點(diǎn)指向的下個結(jié)點(diǎn)
- 設(shè)置該結(jié)點(diǎn)指向的下個結(jié)點(diǎn)
- 設(shè)置該結(jié)點(diǎn)的數(shù)據(jù)
- 獲取該結(jié)點(diǎn)的數(shù)據(jù)
順序表和單鏈表的比較
順序表的主要優(yōu)點(diǎn)是支持隨機(jī)讀取第焰，以及內(nèi)存空間利用效率高；順序表的主要缺點(diǎn)是需要預(yù)先給出數(shù)組的最大數(shù)據(jù)元素個數(shù)妨马，而這通常很難準(zhǔn)確作到挺举。當(dāng)實(shí)際的數(shù)據(jù)元素個數(shù)超過了預(yù)先給出的個數(shù)，會發(fā)生異常烘跺。另外湘纵，順序表插入和刪除操作時需要移動較多的數(shù)據(jù)元素。
和順序表相比滤淳，單鏈表的主要優(yōu)點(diǎn)是不需要預(yù)先給出數(shù)據(jù)元素的最大個數(shù)梧喷。另外，單鏈表插入和刪除操作時不需要移動數(shù)據(jù)元素。 單鏈表的主要缺點(diǎn)是每個結(jié)點(diǎn)中要有一個指針铺敌，因此單鏈表的空間利用率略低于順序表的汇歹。另外，單鏈表不支持隨機(jī)讀取偿凭，單鏈表取數(shù)據(jù)元素操作的時間復(fù)雜度為O（n）产弹；而順序表支持隨機(jī)讀取，順序表取數(shù)據(jù)元素操作的時間復(fù)雜度為O（1）笔喉。
單鏈表的效率分析
在單鏈表的任何位置上插入數(shù)據(jù)元素的概率相等時取视，在單鏈表中插入一個數(shù)據(jù)元素時比較數(shù)據(jù)元素的平均次數(shù)為：
刪除單鏈表的一個數(shù)據(jù)元素時比較數(shù)據(jù)元素的平均次數(shù)為：
因此，單鏈表插入和刪除操作的時間復(fù)雜度均為O（n）常挚。另外作谭，單鏈表取數(shù)據(jù)元素操作的時間復(fù)雜度也為O（n）。
單鏈表實(shí)現(xiàn)
單鏈表節(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)
package com.algorithm.list;
public class ListedNode {
Object element;
ListedNode next;
public ListedNode(ListedNode next){
this.next = next;
}
public ListedNode(Object element, ListedNode next){
this.element = element;
this.next = next;
}
public void setElement(Object element) {
this.element = element;
}
public Object getElement() {
return element;
}
public ListedNode getNext() {
return next;
}
public void setNext(ListedNode next) {
this.next = next;
}
@Override
public String toString() {
return this.element.toString();
}
}
單鏈表實(shí)現(xiàn)
package com.algorithm.list;
import java.time.temporal.Temporal;
public class LinkList implements List {
/**
* 頭指針
*/
private ListedNode head;
/**
* 當(dāng)前節(jié)點(diǎn)對象
*/
private ListedNode current;
/**
* 節(jié)點(diǎn)個數(shù)
*/
private int size;
/**
* 創(chuàng)建空的鏈表
*/
public LinkList() {
// 初始化頭節(jié)點(diǎn)奄毡，頭指針指向頭節(jié)點(diǎn)折欠，當(dāng)前節(jié)點(diǎn)對象等于頭節(jié)點(diǎn)
this.head = current = new ListedNode(null);
// 單項鏈表初始長度
this.size = 0;
}
@Override
public int size() {
return this.size;
}
/**
* 獲取當(dāng)前對象的前一個節(jié)點(diǎn)，將當(dāng)前節(jié)點(diǎn)定位到要操作節(jié)點(diǎn)的前一個元素吼过，思考
* @param index
* @throws Exception
*/
private void index(int index) throws Exception {
// 小于-1锐秦，以首元節(jié)點(diǎn)索引為0，頭節(jié)點(diǎn)為-1
if(index < -1 || index > size - 1){
throw new Exception("參數(shù)錯誤");
}
// 在頭節(jié)點(diǎn)之后操作
if(index == -1){
return;
}
int j = 0;
current = head.next;
while(current != null && j < index){
current = current.next;
j++;
}
}
@Override
public void insert(int index, Object obj) throws Exception {
// TODO Auto-generated method stub
if(index <0 ||index >size)
{
throw new Exception("參數(shù)錯誤盗忱！");
}
//定位到要操作結(jié)點(diǎn)的前一個結(jié)點(diǎn)對象酱床。
index(index-1);
current.setNext(new ListedNode(obj,current.next));
size++;
}
@Override
public void delete(int index) throws Exception {
if(isEmpty()){
throw new Exception("鏈表為空，無法刪除!!");
}
check(index, 0, "參數(shù)范圍錯誤");
index(index - 1);
current.setNext(current.next.next);
this.size --;
}
private void check(int index, int i, String message) throws Exception {
if (index < i || index > size) {
throw new Exception(message);
}
}
@Override
public Object get(int index) throws Exception {
check(index, 0, "參數(shù)范圍錯誤");
index(index);
return current.getElement();
}
@Override
public boolean isEmpty() {
return this.size == 0;
}
public static void main(String[] args) throws Exception {
LinkList list = new LinkList();
for(int i = 0; i < 10; i++){
int t = (int) ((Math.random()*100) % 100);
list.insert(i,t);
System.out.print(t+" ");
}
// 刪除第五個元素
list.delete(4);
System.out.println("刪除之后");
for(int i = 0; i < list.size;i++){
System.out.print(list.get(i) + " ");
}
}
}
