링크 의 이해

1. 링크 는 무엇 입 니까?
2. 링크 는 어떤 특징 이 있 습 니까?
3. 왜 체인 시 계 를 사용 합 니까?
4. 링크 는 몇 가지 형식 으로 나 뉘 나 요?
    직관 적 으로 볼 때 목걸이, 불 주, 시 계 는 모두 링크 의 표현 형식 이 고 링크 는 일련의 결점 으로 구 성 된 데이터 구조 이다.
    링크 의 특징: 링크 는 일련의 노드 로 구성 되 고 모든 노드 는 적어도 두 개의 도 메 인 (데이터 도 메 인과 다음 노드 를 가리 키 는 참조 유형) 을 포함 하 며 양 방향 단일 체인 표 와 순환 단일 체인 표 는 부모 노드 를 가리 키 는 참조 유형 도 메 인 이 있다.링크 에 저 장 된 물리 적 주 소 는 비 연속 적 이 고 링크 는 길 지 않 으 며 언제든지 새로운 노드 를 추가 할 수 있 습 니 다.
    이전에 우 리 는 배열 로 대열 을 실현 한 적 이 있 습 니 다. 배열 로 실현 할 수 있 는 이상 왜 링크 로 대열 을 실현 하 는 방법 을 사용 해 야 합 니까?배열 과 링크 는 도대체 어떤 차이 가 있 습 니까?
    배열 은 길이 가 정 해 져 있 고 배열 은 아래 표 시 를 가지 고 있어 서 배열 이 찾기 가 비교적 편리 하 다. 아래 표 시 를 통 해 찾 고 싶 은 요 소 를 직접 얻 을 수 있다. 배열 로 요 소 를 찾 는 작업 을 할 때 시간 복잡 도 는 1 이 고 배열 에 있 는 요소 가 저 장 된 물리 적 주 소 는 연속 적 이다. 그러면 배열 이 삽입 되 고 삭제 되 는 작업 을 하 는 것 이 비교적 번거롭다.하나의 요 소 를 삽입 하거나 삭제 할 때마다 배열 의 절반 의 데이터 요 소 를 이동 해 야 합 니 다.그러나 링크 는 배열 의 기능 과 반대 되 고 배열 의 장점 은 바로 링크 의 단점 이 며 반대로 도 마찬가지 이다.따라서 데이터 에 대한 조작 에 따라 이 두 가지 방법 을 선택 하여 사용 할 수 있다.삽입 또는 삭제 작업 을 실현 하려 면 링크 를 선택 하 십시오. 링크 는 다음 노드 참조 유형 을 가리 키 는 값 만 수정 하고 시간 복잡 도 는 1 이기 때 문 입 니 다.
    링크 는 선형 링크 와 비 선형 링크 로 나 뉜 다.
    선형 체인 테이블 은 주로 단일 체인 테이블, 양 방향 체인 테이블, 순환 체인 테이블 을 포함한다.
   비 선형 링크 는 주로 나무, 그림 등 을 포함한다.
단일 체인 시트 작업:
링크 로 대기 열 을 실현 하 는 방법:
자바 코드

public void add(Object obj){
		if(root==null){//          
			root=new LinkNode(obj);//          
			end=root;//            
		}
		else{
			LinkNode node=new LinkNode(obj);//        
			end.setNext(node);//       
			end=node;//              
		}
		
	}

  대기 열의 길이:

public int size(){
		int count=0;
		if(root==null){//       
		return 0;//  0
		}
		else{//        ，
			count++;//   +1
			LinkNode node=root.getNext();//           
			while(node!=null){
				count++;//   +1
				 node =node.getNext();
			}
			return count;
		}
	}

 
 아래 표 시 된 요소 에 따라 원 소 를 얻 을 수 있 습 니 다:

public LinkNode get(int index){
		int count=0;
		if(index>=size()||index<0){//            
			throw new RuntimeException("           index="+index);//    
			
		}
		else{
			if(index==0){//     0
				return root;//       
			}
			else{
			LinkNode node=root.getNext();//          
			while(node!=null){//        
				count++;//    +1
				if(index==count){
					return node;
				}
				else 
				node=node.getNext();
			}
		}
		}
		return null;
		
	}

 
 대기 열 에 노드 삽입 하기:

public void insert(LinkNode node,int index){
		if(index<0){//          
			throw new RuntimeException("           index="+index);//    
		}
		else if(index==0){//        0
			node.setNext(root);//             
			root=node;//                 
		}
		else if(index>0&&index<=size()-1){//               ，        
			LinkNode node1=get(index-1);//               
			LinkNode node2=get(index);//               
			node1.setNext(node);//         
			node.setNext(node2);
		}
		else{//           
			end.setNext(node);//             
			end=node;//         
		}
	}

 
 
  열 에 있 는 노드 를 삭제 합 니 다:

public void remove(int index){
		if(index<0||index>=size()){//          
			throw new RuntimeException("           index="+index);//    
		}
		else if(index==0){//        0
			LinkNode node1=root.getNext();//          
			root=node1;//         
		}
		else if(index>0&&index<size()-1){//               ，        
			LinkNode node1=get(index-1);//               
			LinkNode node2=get(index);//          
			node1.setNext(node2.getNext());//                         
		}
		else{//           
			LinkNode node1=get(index-1);//         
			node1.setNext(null);
		}
	}

 
 
 결점 의 값 수정:

public void xiuGai(LinkNode node,int index){
		if(index<0&&index>size()-1){
			throw new RuntimeException("           index="+index);//    
		}
		else {
			LinkNode node1=get(index);
			node1.setObj(node.getObj());
		}
	}

  
 양 방향 링크 의 이해:
양 방향 링크 는 실제 적 으로 단일 링크 표 구조 와 유사 하 다. 단지 단일 링크 표 보다 부모 노드 를 가리 키 는 인용 유형 도 메 인 이 많 을 뿐이다. 따라서 양 방향 링크 를 만 들 때 뿌리 노드 를 제외 한 다른 노드 의 부모 노드 를 가리 키 는 인용 유형 도 메 인 을 그의 앞의 노드 를 가리 키 면 된다.
양 방향 링크 작업:
양 방향 링크 만 들 기:

public static LinkNode creatDoubleLink(String [] a){
		LinkNode root=new LinkNode(a[0]);
		LinkNode node1=new LinkNode(a[1]);
		LinkNode node2=new LinkNode(a[2]);
		LinkNode node3=new LinkNode(a[3]);
		root.setNext(node1);
		node1.setNext(node2);
		node1.setParent(root);
		node2.setParent(node1);
		node2.setNext(node3);
		node3.setParent(node2);
		return root;
	}

 
 
 
 
 
 
양 방향 링크 옮 겨 다 니 기:

public static void printNode(LinkNode root){
		if(root.getNext()!=null){
			Object obj=root.getObj();
			System.out.println("         "+obj);
			LinkNode node=root.getNext();
			printNode(node);
			
		}
		else {
			Object obj=root.getObj();
			System.out.println("         "+obj);
			LinkNode parent=root.getParent();
			while(parent!=null){
				Object ob=parent.getObj();
				System.out.println("         "+ob);
				parent=parent.getParent();
			}
		}
	}

  양 방향 링크 에 요 소 를 삽입 합 니 다:

public static LinkNode insert(LinkNode nodee,int index){
		int count=0;//              ，     ，       
		LinkNode nodeR=creatDoubleLink(root,node);//           
		LinkNode node1=nodeR.getNext();//          
		LinkNode last = null;//         
		if(index<0){//            
			System.out.println("        ！");
		}
		if(index==0){//         
			nodee.setNext(nodeR);
			nodeR.setParent(nodee);
			nodeR=nodee;
		}
		else{//             
			while(node1!=null){//        
				count++;
				if(node1.getNext()==null){//            
					last=node1;//     
				}
				if(count!=index){//            	
				     node1=node1.getNext();
					}
				else {//           
					nodee.setNext(node1);
					nodee.setParent(node1.getParent());
					node1.getParent().setNext(nodee);
					node1.setParent(nodee);
					break;
					}
				}
			if(count<index){//           
				last.setNext(nodee);
				nodee.setParent(last);
			}
				
			}
		return nodeR;
		
	}

 
 
  양 방향 링크 의 지정 한 위치의 결산 점 을 삭제 합 니 다:

public static LinkNode delete(int index){
		int count=0;//                 
		LinkNode nodeR=creatDoubleLink(root,node);//           
		LinkNode nodee=nodeR.getNext();//              
		if(index==0){//          
			nodeR=nodeR.getNext();//             
			nodeR.setParent(null);//       ，             Null
			
		}
		else{//          
			while(nodee!=null){
				count++;
				if(count!=index){//       
					nodee=nodee.getNext();// node   ，           
				}
				else{
					if(nodee.getNext()!=null){//             
						nodee.getParent().setNext(nodee.getNext());
						nodee.getNext().setParent(nodee.getParent());
					}
					else{//          
						nodee.getParent().setNext(null);
					}
				}
			}
			if(count<index){
				System.out.println("         ！");
				return null;
			}
			
		}
		return nodeR;
	}

 
 순환 링크: 링크 를 지정 할 때 이 링크 에 고리 가 있 는 지 판단 합 니 다.
순환 링크 만 들 기:

public static LinkNode createCircleList(String [] sa){
		LinkNode root=new LinkNode(sa[0]);
		LinkNode node1=new LinkNode(sa[1]);
		LinkNode node2=new LinkNode(sa[2]);
		LinkNode node3=new LinkNode(sa[3]);
		LinkNode node4=new LinkNode(sa[4]);
		root.setNext(node1);
		node1.setNext(node2);
		node2.setNext(node3);
		node3.setNext(node4);
		//node4.setNext(root);
		return node3;
	}

 
 
 순환 링크 에 링 이 있 는 지 판단 하기:

public static boolean isCircle(LinkNode root){
		LinkNode fast=root;
		LinkNode slow=root;
		while(fast!=null&&fast.getNext()!=null){
			fast=fast.getNext().getNext();
			slow=slow.getNext();
			if(fast==slow){
				return true;
			}

 위 에 쓰 인 양 방향 링크 와 순환 링크 의 생 성 방법 은 너무 번 거 로 워 서 약간 수정 되 었 습 니 다.
양 방향 링크 생 성:

public static LinkNode creatDoubleLink(LinkNode root,LinkNode node){
		if(root!=null&&biaoji<a.length-1){//        ，          
		biaoji++;//     +1
		node=new LinkNode(a[biaoji]);//          
		root.setNext(node);//       
		node.setParent(root);
		LinkNode node1=null;
		creatDoubleLink(node,node1);//    
		}
		return root;
	}

 단 방향 순환 링크 생 성:

public static LinkNode createCircleLink(LinkNode node1){
		if(biaoji!=sa.length-1&&root!=null){//           
			biaoji++;
			   LinkNode	node=new LinkNode(sa[biaoji]);
			   if(biaoji==sa.length-1){
				   nodee=node;//        
			   }
			   node1.setNext(node);//         
			   createCircleLink(node);//    
			   
		}
		else{//         
			nodee.setNext(root);//                 
			}
		return root;
	}