單向連結串列

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

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通過迴圈獲得指定元素 , 還有就是連結串列的刪除和插入的原理 . 一定要熟記