單向鏈表

這個是資料結構中最為基礎的兩大結構之一,后面的堆疊和佇列都會用到單向鏈表作為底層,所以學好了單向鏈表你就成功了一大半了!

1,鏈表都必須的東西----節點物件node

public class Node {
	private Object data; //存放資料
	private Node next;	//存放指標
	
	public Node(Object data, Node next) {
		this.data = data;
		this.next = next;
	}
	public Node(Object data) {
		this.data = data;
		this.next=null;
	}
	
	public Node() {
		this.data=null;
		this.next=null;
	}
	public Object getData() {
		return data;
	}
	public void setData(Object data) {
		this.data = data;
	}
	public Node getNext() {
		return next;
	}
	public void setNext(Node next) {
		this.next = next;
	}
}

這個節點物件很容易理解就是兩個屬性一個用來存放資料data,另一個存放指標next指向下一個物件資料

2,創建介面用來定義方法

public interface MyList {
	public void clear(); 		//讓鏈表為空
	public boolean isEmpty(); 	//判斷鏈表是否為空
	public int length();		//回傳鏈表中的元素長度
	public Object get(int i);	//獲得指定索引上的元素
	public void insert(int i,Object x)throws Exception; 	//在指定索引位置上插入指定資料
	public void add(Object x) throws Exception;				//插入指定資料
	public void remove(int i)throws Exception;				//洗掉指定索引上的元素
	public void delete(Object x)throws Exception;			//洗掉指定元素
	public void printList() ;	//遍歷鏈表中的所有元素
	public int getData(Object x);	//獲得指定元素的索引
}

你也可以不寫介面但是寫介面會顯得更專業一點

3,撰寫一個實作類

public class MyLinkedList implements MyList{
    private Node header;//頭節點
	private int size;//元素個數
	
	public MyLinkedList() {
		this.header=new Node(null);
		this.size=0;
	}
}

這里的構造方法是為了初始化的作用 , 創建一個新的node物件不給他賦值用來作為一個頭結點 , 這個頭節點不用存盤資料 . 然后初始化size的個數為0.*

這個就是鏈表的基本結構

4,實作介面中的方法

1,clear,isEmpty,length三個簡單一點的方法

	@Override
	public void clear() {
		header.setNext(null);
	}

	@Override
	public boolean isEmpty() {
		return this.size==0;
	}

	@Override
	public int length() {
		return this.size;
	}

clear方法 : 直接讓頭節點的下一位指標指向一個空;

isEmpty方法 : 直接回傳size屬性是否為0用來判斷該鏈表是否為空

length方法 : 直接回傳size的值就為鏈表的有效長度

2,add,insert兩個添加方法

	@Override
	public void insert(int i, Object x) throws Exception {
		if(i<0||i>=size) {
			throw new Exception("索引不合法");
		}
		Node newNode=new Node(x);
		Node temp=header.getNext();
		while(temp.getNext()!=null && i>=0) {
			temp=temp.getNext();
			i--;
		}
		newNode.setNext(temp.getNext());
		temp.setNext(newNode);
		size++;
	}

	@Override
	public void add(Object x) throws Exception {
		Node newNode=new Node(x);
		if(size==0) {
			header.setNext(newNode);
		}else{
			Node temp=header.getNext();
			while(temp.getNext()!=null) {
				temp=temp.getNext();
			}
			temp.setNext(newNode);
		}
		size++;
		
	}

insert方法 :

1,判斷索引的取值是否合法 如果索引小于0則不合法 , 如果索引大于size有效元素的個數則索引不合法

2,創建一個node物件newNode并且用構造方法傳入指定元素x.

3,創建一個node物件temp用來存盤與header節點連接的第一個資料

4,while回圈將指定索引上面的資料通過回圈存入temp中

5,將指定索引上資料temp的下一位資料拼在newNode的屁股后面

6,然后再把newNode拼接在temp的后面這樣鏈表就連接起來了

7,size的個數加一

add方法 :

1,創建一個node物件newNode并且用構造方法傳入指定元素x.

2,判斷size是否為0 , 如果是則證明這個鏈表為空,就直接把元素插在header頭節點的后面第一個

3,創建一個node物件temp用來存盤與header節點連接的第一個資料

4,while回圈將指定索引上面的資料通過回圈存入temp中

5,一直遍歷到最后一個元素然后存在temp中,然后將我們指定的newNode元素接在temp的后面

6,size的個數加一

add和insert方法基本思路是一樣的 , 如果指定了索引就通過回圈找出索引位置的資料在他后面添加新資料 , 然后把指定位置資料的后一個資料跟newNode連接 . 如果沒有指定索引那就簡單了直接回圈到最后一個元素然后接在后面

3,remove和delete兩個洗掉方法

@Override
	public void remove(int i) throws Exception {
		if(size==0) {
			System.out.println("沒有元素");
		}else {
			int k=0;
			Node temp=header.getNext();
			Node prTemp=header;
			while(temp.getNext()!=null) {
				if(k==i) {
					prTemp.setNext(temp.getNext());
				}
				prTemp=temp;
				k++;
				temp=temp.getNext();
			}
			size--;
		}
		
	}

	@Override
	public void delete(Object x) throws Exception {
		if(size==0) {
			System.out.println("滿了");
		}else {
			Node temp=header.getNext();
			Node prTemp=header;
			while(temp.getNext()!=null) {
				if(temp.getData()==x) {
					prTemp.setNext(temp.getNext());
				}
				prTemp=temp;
				temp=temp.getNext();
			}
			size--;
		}
	}

remove方法 :

1,首先判斷鏈表的有效元素個數size的大小 , 如果size==0就說明這個鏈表是空的沒有元素 , 直接回傳無元素或者拋出例外

2,創建一個int型別的k作為計數用

3,如果有元素那么創建temp存放header頭節點的下一個元素

4,創建一個新的node節點prtemp物件存入header頭節點

5,通過回圈把指定索引前面的第一個元素存入prtemp中

6,通過while回圈獲取到指定索引位置的資料存入temp中

7,如果k==i那么此時temp存入的是指定索引的資料 , 而prtemp中存入的是指定索引資料的前一個資料 , 此時只需要把prtemp的next指標指向temp的下一位這樣就可以直接將索引位置的資料洗掉

8,有效個數size–;

delete方法 :

1,首先判斷鏈表的有效元素個數size的大小 , 如果size==0就說明這個鏈表是空的沒有元素 , 直接回傳無元素或者拋出例外

2,如果有元素那么創建temp存放header頭節點的下一個元素

3,創建一個新的node節點prtemp物件存入header頭節點

4,通過回圈把指定索引前面的第一個元素存入prtemp中

5,通過while回圈獲取到指定索引位置的資料存入temp中

6,如果temp中存入的資料temp.getdata==x那么此時temp存入的是指定索引的資料 , 而prtemp中存入的是指定索引資料的前一個資料 , 此時只需要把prtemp的next指標指向temp的下一位這樣就可以直接將索引位置的資料洗掉

7,有效個數size–;

**remove和delete方法都有異曲同工之妙創建了pretemp和temp物件用來存盤指定元素前面一個元素和指定元素 , 洗掉操作也很簡單就是通過讓指定元素前后指標繞開他與后面連接 , 就會形成沒有指標指向指定元素從而達到洗掉效果 **

get方法 :

@Override
	public Object get(int i) {
		if(size==0) {
			System.out.println("沒元素");
		}else {
			Node temp=header.getNext();
			while(temp.getNext()!=null && i>=0) {
				temp=temp.getNext();
				i--;
			}
			return temp.getData();
		}
		return null;
	}

1,首先判斷鏈表的有效元素個數size的大小 , 如果size==0就說明這個鏈表是空的沒有元素 , 直接回傳無元素或者拋出例外

2,如果有元素那么創建temp存放header頭節點的下一個元素

3,通過while回圈獲取到指定索引位置的資料存入temp中

4,回傳temp中的data就是指定索引上的元素

5,如果不滿足就回傳null

getData方法 :

@Override
	public int getData(Object x) {
		if(size==0) {
			System.out.println("無元素");
		}else {
			int i=0;
			Node temp=header.getNext();
			while(temp.getNext()!=null) {
				if(temp.getData()==x) {
					return i;
				}
				i++;
				temp=temp.getNext();
			}
		}
		return -1;
	}

1,首先判斷鏈表的有效元素個數size的大小 , 如果size==0就說明這個鏈表是空的沒有元素 , 直接回傳無元素或者拋出例外

2,設定int型別的i作為計數

3,如果有元素那么創建temp存放header頭節點的下一個元素

4,通過回圈獲得data==x的資料存入temp中

5,i的值為回圈的次數同時也是索引的值

get和getData方法都很像通過回圈獲得了指定位置的資料存入temp中然后 , 用int型別的變數進行計數獲得索引.

printList方法

@Override
	public void printList() {
		if(size==0) {
			System.out.println("無元素");
		}else {
			Node temp=header.getNext();
			while(temp.getNext()!=null) {
				System.out.print(temp.getData()+" , ");
				temp=temp.getNext();
			}
			System.out.println(temp.getData());
		}
		
	}

1,首先判斷鏈表的有效元素個數size的大小 , 如果size==0就說明這個鏈表是空的沒有元素 , 直接回傳無元素或者拋出例外

2,如果有元素那么創建temp存放header頭節點的下一個元素

3,每一次都輸出temp中data的值

最后發一下整體代碼

public class MyLinkedList implements MyList{

	private Node header;//頭節點
	private int size;//元素個數
	
	public MyLinkedList() {
		this.header=new Node(null);
		this.size=0;
	}

	@Override
	public void clear() {
		header.setNext(null);
	}

	@Override
	public boolean isEmpty() {
		return this.size==0;
	}

	@Override
	public int length() {
		return this.size;
	}

	@Override
	public Object get(int i) {
		if(size==0) {
			System.out.println("沒元素");
		}else {
			Node temp=header.getNext();
			while(temp.getNext()!=null && i>=0) {
				temp=temp.getNext();
				i--;
			}
			return temp.getData();
		}
		return null;
	}

	@Override
	public void insert(int i, Object x) throws Exception {
		if(i<0||i>=size) {
			throw new Exception("索引不合法");
		}
		Node newNode=new Node(x);
		Node temp=header.getNext();
		while(temp.getNext()!=null && i>=0) {
			temp=temp.getNext();
			i--;
		}
		newNode.setNext(temp.getNext());
		temp.setNext(newNode);
		size++;
	}

	@Override
	public void add(Object x) throws Exception {
		Node newNode=new Node(x);
		if(size==0) {
			header.setNext(newNode);
		}else{
			Node temp=header.getNext();
			while(temp.getNext()!=null) {
				temp=temp.getNext();
			}
			temp.setNext(newNode);
		}
		size++;
	}

	@Override
	public void remove(int i) throws Exception {
		if(size==0) {
			System.out.println("滿了");
		}else {
			int k=0;
			Node temp=header.getNext();
			Node prTemp=header;
			while(temp.getNext()!=null) {
				if(k==i) {
					prTemp.setNext(temp.getNext());
				}
				prTemp=temp;
				k++;
				temp=temp.getNext();
			}
			size--;
		}
		
	}

	@Override
	public void delete(Object x) throws Exception {
		if(size==0) {
			System.out.println("無元素");
		}else {
			Node temp=header.getNext();
			Node prTemp=header;
			while(temp.getNext()!=null) {
				if(temp.getData()==x) {
					prTemp.setNext(temp.getNext());
				}
				prTemp=temp;
				temp=temp.getNext();
			}
			size--;
		}
	}

	@Override
	public void printList() {
		if(size==0) {
			System.out.println("無元素");
		}else {
			Node temp=header.getNext();
			while(temp.getNext()!=null) {
				System.out.print(temp.getData()+" , ");
				temp=temp.getNext();
			}
			System.out.println(temp.getData());
		}
		
	}

	@Override
	public int getData(Object x) {
		if(size==0) {
			System.out.println("無元素");
		}else {
			int i=0;
			Node temp=header.getNext();
			while(temp.getNext()!=null) {
				if(temp.getData()==x) {
					return i;
				}
				i++;
				temp=temp.getNext();
			}
		}
		return -1;
	}    
}

										**小結**

單鏈串列是資料結構中最為基礎的結構我們必須要牢記并且熟練掌握 , 本身不是很難我們需要理解的是temp通過回圈獲得指定元素 , 還有就是鏈表的洗掉和插入的原理 . 一定要熟記