《算法》---- 單連結清單和雙連結清單基礎(SingleLinkedList & DoubleLinkedList)

目錄

• Single Linked List
• • 構造連結清單
  • 在表頭插入結點
  • 在表尾插入結點
  • 從表頭删除結點
  • 在表尾删除結點
  • 其他位置的插入和删除操作
  • 周遊
• Double Linked List
• • 構造連結清單
  • 在表頭插入結點
  • 從表頭删除結點
  • 在表尾插入結點
  • 在表尾删除結點
  • 其他位置的插入和删除操作

Single Linked List

構造連結清單

public class Node {
	public Object value;
	public Node next;
	
	public Node(Object value,Node next) {
		this.value=value;
		this.next=next;
	}
	
	public Node(Object value) {
		this.value=value;
		this.next=null;
	}

	public Object getValue() {
		return value;
	}

	public void setValue(Object value) {
		this.value = value;
	}

	public Node getNext() {
		return next;
	}

	public void setNext(Node next) {
		this.next = next;
	}
}

           

在表頭插入結點

public class SingleLikedList {
	private Node head;
	private Node current;
	private int size;
	
	public SingleLikedList() {
		head = current = new Node(null);
		size=0;
	}
	public boolean isEmpty(){
		return size==0;
	}
	 
	public int getSize(){
		return size;
	}
	public void addFirst(Object obj) {
		Node temp = head;
		head=new Node(obj,temp);
		size++;
	}
}
           

在表尾插入結點

接上

public void addLast(Object obj) {
	Node newNode = new Node(obj);
	current=head.next;
	//找到目前尾結點
	while(current.next != null) {
		current = current.next;
	}
	current.next=newNode;
	size++;
}
           

從表頭删除結點

接上

public void deleteFirst() {
	head = head.next;
	size--;
}
           

在表尾删除結點

接上

public void deleteLast() {
	current=head.next;
	//找到倒數第二個尾結
	while(current.next.next != null) {
		current = current.next;
	}
	current.next=null;
	size--;
}
           

其他位置的插入和删除操作

public void insert(int position, Object obj) {
	if(position<1 || position>size) {throw new IndexOutOfBoundsException ("Wrong Position");}
	if(position==1) {addFirst(obj);}
	else if(position==size) {addLast(obj);}
	else {
		Node newNode = new Node(obj);
		current = head;
		//找到插入位置的前一個位置
		for(int i=1; i<position-1; i++) {
			current = current.next;
		}
		Node temp = current.next;
		current.next = newNode;
		newNode.next = temp;
		size++;
	}
	
}

public void delect(int position) {
	if(position<1 || position>size) {throw new IndexOutOfBoundsException ("Wrong Position");}
	if(position==1) {deleteFirst();}
	else if(position==size) {deleteLast();}
	else {
		current = head;
		for(int i=1; i<position-1; i++) {
			current = current.next;
		}
		current.next = current.next.next;
	}
}
           

周遊

for(Node x=first; x!=null; x=x.next) {
		System.out.println(x.item);
}
           

Double Linked List

構造連結清單

public class Node {
	public Object value;
	public Node next;
	public Node previous;
	
	public Node(Object value,Node previous, Node next) {
		this.value=value;
		this.previous = previous;
		this.next=next;
	}
	
	public Node(Object value) {
		this.value=value;
		this.next=null;
		this.previous=null;
	}

	public Object getValue() {
		return value;
	}

	public void setValue(Object value) {
		this.value = value;
	}

	public Node getPrevious() {
		return previous;
	}

	public void setPrevious(Node previous) {
		this.previous = previous;
	}
	public Node getNext() {
		return next;
	}

	public void setNext(Node next) {
		this.next = next;
	}
}

           

在表頭插入結點

public class DoubleLinkedList {
	private Node head;
	private Node tail;
	private Node current;
	private int size;
	
	public DoubleLinkedList() {
		head=tail=current=new Node(null);
		size=0;
	}
	
	public void addFirst(Object obj) {
		head = new Node(obj,null,head);
		if(size==0) {tail=head;}
		else {head.next.previous=head;}
		size++;
	}
}
           

從表頭删除結點

接上

public void deleteFirst() {
	head = head.next;
	head.previous = null;
	size--;
}
           

在表尾插入結點

接上

public void addLast(Object obj) {
	tail = new Node(obj,tail,null);
	if(size==0) {head=tail;}
	else {tail.previous.next=tail;}
	size++;
}
           

在表尾删除結點

接上

public void deleteLast() {
	tail = tail.previous;
	if(tail==null) {head = null;}
	else {
		tail.next = null;
	}
	size--;	
}
           

其他位置的插入和删除操作

public void insert(int position, Object obj) {
	if(position<1) {throw new IndexOutOfBoundsException ("Wrong Position");}
	else if(position==1) {addFirst(obj);}
	else if(position==size) {addLast(obj);}
	else {
		current=head;
		for(int i=1; i<position-1; i++) {
			current=current.next;
		}
		current.next = new Node(obj,current,current.next);
		current.next.next.previous = current.next; 
		size++;
	}
}

public void delete(int position) {
	if(position<1) {throw new IndexOutOfBoundsException ("Wrong Position");}
	else if(position==1) {deleteFirst();}
	else if(position==size) {deleteLast();}
	else {
		current=head;
		for(int i=1; i<position-1; i++) {
			current=current.next;
		}
		current.next = current.next.next;
		current.next.next.previous= current.next;
		size--;
	}
}