Dynamic linked list 4 one-way circular linked list (loopsingle Implementation)

    1. The definition of unidirectional circular linked list .

•       One way circular linked list element storage and queue sequential storage ArrayQueueLoop Of Optimize It's kind of like , Elements are connected around ,( Store elements ) Like a ring structure , Not a straight line .
•       One way circular linked list diagram .

•       When the one-way circular linked list is empty , The head pointer head And tail pointer rear At the same time point to a null.

•       The interface implemented by the one-way circular linked list is List, Unlike stack chain LinkedStack And queue linked list LinkedQueue The same is equivalent to calling the chain of linear tables LinkedList.

    2.LoopSingle The definition of .

    list： It is a one-way circular linked list LoopSingle Interface class to be implemented .

    Node：

                  1、 It is a one-way circular linked list LoopSingle The inner class of .

                  2、E data It's the data domain , Used to store elements .

                  3、E next It's a pointer field , The address used to store the next element .

                  4、Node() Is a parameterless constructor , establish Node The object of , If no value is passed, this constructor will be called by default .

                  5、Node(E data,Node null) Is a parameterized constructor , establish Node When an object of type , Pass the value, then call this constructor .

    LoopSingle：

                  1、Node head It's the head pointer , Is to define a Node Type of head Variable . Used to store the first element .

                  2、Node rear    Is the tail pointer , Is to define a Node Type of rear Variable . Used to store the last element , It can also be used to .next To connect the first element , Form a circular linked list .

                  3、int size It's a variable , There are several elements in the circular linked list used to store records .

                  4、LoopSingle() It is the parameterless constructor of the circular linked list , When the main function creates an object of this class , Call this constructor without passing a value .

                  5、LoopSingle(E[] arr) It is a circular linked list with parameter constructor , When the main function creates this kind of object , This constructor is called when passing values .

                  6、boolean equals(Object obj) It is a content comparison method of circular linked list .

                  7、String toString() It is a text representation method of circular linked list .

    3. One way circular linked list elements into the chain .

      1、 First, judge whether the inserted position is out of range , If it exceeds, throw an exception .

      2、 Create another Node Variable of type n, Used to store the data of inserted elements .

      3、 Then judge the elements size Is the value of 0, That is, the head pointer head And tail pointer rear All point to one null. If established, directly put the head pointer head And tail pointer rear Move to the first element position , Then put the tail pointer rear The next jump points to the head pointer hear The location of , That is to say n It's about .      

      4、 Then determine whether the insertion position is index=0 The location of , If yes, point the next jump of the tail pointer to n,n The next jump points to the head pointer head, Then put the head pointer head Move to n It's about .

      5、 Then judge index Is it tail insertion , That is to say index=size, Yes, it will n The next jump of points to head, Then put the head pointer head The next jump of points to n, Finally, put the head pointer head Move to n It's about .

      6、 Finally, if the insertion position is the internal position of the head and tail , Create a Node Type of p Equals the header pointer head, It is mainly used to traverse to the last element at the insertion position . Then when you reach the position , Proceed to n The next jump of points to p The next jump , The final will be p The next jump of points to n.

      7、 Remember the element record symbol every time you insert an element size Add up 1.

public void add(int index, E e) {
		if(index<0||index>size){         //1
			throw new IllegalArgumentException(" Illegal insertion of corner marks !");
		}
		Node n=new Node(e,null);         //2
		if(isEmpty()){	// A special case           3
			head=n;
			rear=n;
			rear.next=head;   // Circular linked list  
		}else if(index==0){	// Head insertion      4
			rear.next=n;
			n.next=head;
			head=n;
		}else if(index==size){// Tail insertion        5
			n.next=head;
			rear.next=n;
			rear=n;
		}else{	// General situation                  6
			Node p=head;
			for(int i=0;i<index-1;i++){
				p=p.next;
			}
			n.next=p.next;
			p.next=n;
		}
		size++;                         //7
	}

    4. Delete the elements of the one-way circular linked list .

      1、 First, judge whether the inserted position is out of range , If it exceeds, throw an exception .

      2、 Create another generic E The variable of res, First use it to store one null. In fact, it is to store the data of deleted elements

      3、 Then judge the elements size Is the value of 1, That is, there is only one element in the whole linked list , Then delete it . Make res Store the data of deleted elements , Then let the head pointer hear And tail pointer rear All point to one null.   

      4、 Then judge whether the deletion location is index=0 The location of , If yes, continue res Store the data of deleted elements , That is to say head.data. Then put the head pointer head Move to the next hop position .

      5、 Then judge index Is it tail deletion , That is to say index=size, If yes, continue res Store the data of deleted elements , That is to say rear.data, Here you need to create a Node Variable of type p, It mainly needs traversal to make p Move to the previous position of the deleted element . When you arrive, start to let p The next jump of points to the tail pointer rear The next jump , Finally, make the tail rear Move to p It's about .

      6、 Finally, if the deletion position is the internal position of the head and tail , Create a Node Type of p Equals the header pointer , It is mainly used to traverse to the last element of the deletion position . Then when you reach the position , Create a Node Type of del For storage p Next hop data , In fact, it is to delete the data of element position . Then let the previous definition res Deposit del.data, The final will be p The next jump of points to del Your next jump is finished .

      7、 Remember the element record symbol every time you delete an element size To cut down 1.

public E remove(int index) {
		if(index<0||index>=size){         //1
			throw new IllegalArgumentException(" It is illegal to delete corner marks !");
		}
		E res=null;                       //2
		if(size==1){	// A special case          //3
			res=head.data;
			head=null;
			rear=null;
		}else if(index==0){               //4
			res=head.data;
			head=head.next;
			rear.next=head;
		}else if(index==size-1){          //5
			res=rear.data;
			Node p=head;     
			while(p.next!=rear){
				p=p.next;
			}
			p.next=rear.next;
			rear=p;
		}else{                            //6
			Node p=head;
			for(int i=0;i<index-1;i++){
				p=p.next;
			}
			Node del=p.next;
			res=del.data;
			p.next=del.next;
		}
		size--;                           //7
		return res;  
	}

    5. Element modification of one-way circular linked list .

      1、 First judge whether the corner mark that needs to be modified is legal , Illegal throw exception handling .

      2、 Then judge the position that needs to be modified , If the modified position is a header pointer head The element of location , Direct header pointer head.data be equal to e.

      3、 Then judge whether the modified position is the last element of the linked list , If yes, make the tail pointer directly rear.data be equal to e.

      4、 Finally, modify the element in the middle of the head and tail pointer , Create a Node Variable of type p, Used to traverse to the location of the modified element , Immediate order p.data be equal to e The modification is completed .

public void set(int index, E e) {
		if(index<0||index>=size){              //1
			throw new IllegalArgumentException(" It is illegal to modify the corner mark !");
		}
		if(index==0){                          //2
			head.data=e;
		}else if(index==size-1){               //3
			rear.data=e;
		}else{                                 //4
			Node p=head;
			for(int i=0;i<index;i++){
				p=p.next;
			}
			p.data=e;
		}
	}

    6. Element search of one-way circular linked list .      

      1、 First judge whether the circular linked list is empty , If it is empty, it directly returns an initial value -1.

      2、 And then create a Node Variable of type p Equals the header pointer head The data of , Mainly used to traverse the linked list down . Add a definition index by 0, It's used to record where you go .

      3、 Start a while loop , Condition is p.data It's not equal to e. The content of the loop is p Every time it points to p The next jump , Point to the post recording position , That is to make index Add up 1, Then judge the position p Whether to cycle back to the head pointer head It's in place , Go back , Return to the end of the loop -1.

      4、 At the end of the cycle , If you find that there is equal to in the linked list e The elements of , So finally back index, That is, record the variable value of the position .

public int find(E e) {
		if(isEmpty()){      //1
			return -1;
		}
		Node p=head;        //2
		int index=0;        //2
		while(p.data!=e){   //3
			p=p.next;
			index++;
			if(p==head){
				return -1;
			}
		}
		return index;       //4
	}

    7. Comparison method of one-way circular linked list .

      1、 First, check the incoming object obj Determine whether it is null , If it is blank, return false.

      2、 For this object obj And this Judge directly whether it is equal , Equality directly returns true.

      3、 Finally, compare the contents , take obj Strong conversion LoopSingle<E> Can start .

      4、 Then judge whether the sum of the elements of the two objects is equal , Equality begins with defining a for loop , from 0~getSize() Position shifting , There are two more objects in the loop, and each position compares elements , Return if not equal false,for There is no difference after the cycle runs , Then you can go back true 了 .

public boolean equals(Object obj) {
		if(obj==null){              //1
			return false;
		}
		if(obj==this){              //2
			return true;
		}
		if(obj instanceof LoopSingle){
			LoopSingle<E> l=(LoopSingle<E>) obj;   //3
			if(this.getSize()==l.getSize()){       //4
				for(int i=0;i<getSize();i++){
					if(get(i)!=l.get(i)){
						return false;
					}
				}
				return true;
			}
		}
		
		return false;
	}

    8. Text output method of one-way circular linked list .

      1、 It's not safe to use threads StringBuilder Class creation object sb.

      2、 Judge whether the cycle chain is empty , Empty to return directly to sb.append("[ ]");.

      3、 If it is not empty, connect first sb.append("[");.

      4、 Then create a Node Type of p Variable , First store the head pointer head The data of .

      5、 Then start a while The cycle of , The cycle condition is true, Start connecting p.data, That's the element , Then add a comma after the judgment , Or on the ] . Only if the conditions are met p.data be equal to rear.data Connect when ] . Add a comma after other elements ,. After each connection ] Or commas , Remember later p Point to p The next jump .

public String toString() {
		StringBuilder sb=new StringBuilder();           //1
		sb.append("LoopSingle:size="+getSize()+"\n");
		if(isEmpty()){                                  //2
			sb.append("[]");
		}else{
			sb.append('[');                             //3
			Node p=head;                                //4
			while(true){                                //5
				sb.append(p.data);
				if(p.next==head){
					sb.append(']');
					break;
				}else{
					sb.append(',');
				}
				p=p.next;
			}
		}
		return sb.toString();
	}

    9. One way circular linked list of all code implementation .

package com.oupeng.p5 Linked list ;

import com.oupeng.p1 The linear table .List;

public class LoopSingle<E> implements List<E> {
	
	private class Node{
		E data;		// Data fields 
		Node next;	// Pointer to the domain 
		@SuppressWarnings("unused")
		public Node(){
			this(null,null);           // Parameter free constructor 
		}
		public Node(E data,Node next){// Elements || Data fields        Address || Pointer to the domain 
			this.data=data;
			this.next=next;
		}
		@Override
		public String toString() {     // Data toString Method 
			return data.toString();
		}
	}
	private Node head;                // Header pointer variable Node type 
	private Node rear;                // Tail pointer variable Node type 
	private int size;                 // Number of record elements 
	
	public LoopSingle() {             // Nonparametric constructor of one-way circular linked list 
		head=null;
		rear=null;
		size=0;
	}
	public LoopSingle(E[] arr){       // Parametric constructor of one-way circular linked list 
		
	}
	
	@Override
	public int getSize() {            // How to get the sum of elements 
		return size;
	}

	@Override
	public boolean isEmpty() {        // Judge whether the one-way circular linked list is empty 
		return size==0&&head==null&&rear==null;
	}
	
	@Override
	public void add(int index, E e) {  // One way circular linked list insert element method 
		if(index<0||index>size){         
			throw new IllegalArgumentException(" Illegal insertion of corner marks !");
		}
		Node n=new Node(e,null);         
		if(isEmpty()){	// A special case                  
			head=n;
			rear=n;
			rear.next=head;   // Circular linked list  
		}else if(index==0){	// Head insertion                 
			rear.next=n;
			n.next=head;
			head=n;
		}else if(index==size){// Tail insertion             
			n.next=head;
			rear.next=n;
			rear=n;
		}else{	// General situation                               
			Node p=head;
			for(int i=0;i<index-1;i++){
				p=p.next;
			}
			n.next=p.next;
			p.next=n;
		}
		size++;                         
	}

	@Override
	public void addFirst(E e) {      // Head insertion 
		add(0,e);
	}

	@Override
	public void addLast(E e) {       // Tail insertion 
		add(size,e);
	}

	@Override 
	public E get(int index) {        // Element acquisition of one-way circular linked list 
		if(index<0||index>=size){
			throw new IllegalArgumentException(" Illegal search for corner marks !");
		}
		if(index==0){
			return head.data;
		}else if(index==size-1){
			return rear.data;
		}else{
			Node p=head;
			for(int i=0;i<index;i++){
				p=p.next;
			}
			return p.data;
		}
	}

	@Override
	public E getFirst() {         // Get the header pointer element 
		return get(0);
	}

	@Override
	public E getLast() {          // Tail pointer element get 
		return get(size-1);
	}

	@Override
	public void set(int index, E e) {      // Element modification of one-way loop mode 
		if(index<0||index>=size){
			throw new IllegalArgumentException(" It is illegal to modify the corner mark !");
		}
		if(index==0){
			head.data=e;
		}else if(index==size-1){
			rear.data=e;
		}else{
			Node p=head;
			for(int i=0;i<index;i++){
				p=p.next;
			}
			p.data=e;
		}
	}

	@Override
	public boolean contains(E e) {        // Judge whether the one-way circular linked list contains e Elements 
		return find(e)!=-1;
	}

	@Override
	public int find(E e) {                // Get the elements of the one-way circular linked list e The location of 
		if(isEmpty()){
			return -1;
		}
		Node p=head;
		int index=0;
		while(p.data!=e){
			p=p.next;
			index++;
			if(p==head){
				return -1;
			}
		}
		return index;
	}

	@Override
	public E remove(int index) {        // Delete the elements of the one-way circular linked list 
		if(index<0||index>=size){
			throw new IllegalArgumentException(" It is illegal to delete corner marks !");
		}
		E res=null;
		if(size==1){	// A special case 
			res=head.data;
			head=null;
			rear=null;
		}else if(index==0){
			res=head.data;
			head=head.next;
			rear.next=head;
		}else if(index==size-1){
			res=rear.data;
			Node p=head;
			while(p.next!=rear){
				p=p.next;
			}
			p.next=rear.next;
			rear=p;
		}else{
			Node p=head;
			for(int i=0;i<index-1;i++){
				p=p.next;
			}
			Node del=p.next;
			res=del.data;
			p.next=del.next;
		}
		size--;
		return res;
	}

	@Override
	public E removeFirst() {         // Head deletion 
		return remove(0);
	}

	@Override
	public E removeLast() {         // Deletion at the end 
		return remove(size-1);
	}

	@Override
	public void removeElement(E e) { // Deletes the specified element e
		remove(find(e));
	}

	@Override
	public void clear() {            // The emptying method of one-way circular linked list 
		head=null;
		rear=null;
		size=0;
 	}
    @Override
	public boolean equals(Object obj) {   // The method to judge whether the contents of two objects are equal 
		if(obj==null){              
			return false;
		}
		if(obj==this){              
			return true;
		}
		if(obj instanceof LoopSingle){
			LoopSingle<E> l=(LoopSingle<E>) obj;   
			if(this.getSize()==l.getSize()){       
				for(int i=0;i<getSize();i++){
					if(get(i)!=l.get(i)){
						return false;
					}
				}
				return true;
			}
		}
		
		return false;
	}
	@Override
	public String toString() {   // The method of text mode output of one-way circular linked list 
		StringBuilder sb=new StringBuilder();
		sb.append("LoopSingle:size="+getSize()+"\n");
		if(isEmpty()){
			sb.append("[]");
		}else{
			sb.append('[');
			Node p=head;
			while(true){
				sb.append(p.data);
				if(p.next==head){
					sb.append(']');
					break;
				}else{
					sb.append(',');
				}
				p=p.next;
			}
		}
		return sb.toString();
	}
}