자바 데이터 구조 총화 (배열, 링크, 더미, 스 택 포함)

더 읽 기
      눈 깜짝 할 사이 에 우 리 는 데이터 구조 에 올 라 갔다. 배열 에서 대기 열 까지 데이터 구조 중의 기본 내용 도 곧 끝 날 것 이다. 배열 의 학습 에서 우 리 는 먼저 Array List 를 배 워 서 간단 한 길이 가 변 적 인 배열 을 만 들 었 다. 두 배열 의 교환 데 이 터 를 이용 하여 매번 증 가 량 이 1 인 가 변 배열 을 만 들 었 으 나 Array List 와 비교 했다.우리 의 가 변 배열 의 계산 속도 가 너무 오래 걸 립 니 다. 배열 의 시간 을 단축 시 키 고 배열 의 효율 을 높이 기 위해 우 리 는 증분, 초기 용량 과 수량 을 설 치 했 습 니 다. 매번 배열 에 데 이 터 를 넣 으 면 배열 자체 의 용량 을 초과 하면 자동 으로 일정한 증 가 를 확대 하여 배열 이 매번 메모리 공간 을 개척 하 는 시간 을 절약 하고 효율 을 높 였 습 니 다. 코드 는 다음 과 같 습 니 다.
     
   단순 길이 가 변 배열
 
 
public class MyList {
	//          0        
	private Object[] src = new Object[0];

	//       Element
	public void add(E s) {
		//        ,         +1
		Object[] dest = new Object[src.length + 1];
		//              
		for(int i=0;i= src.length) {
			//       
			IndexOutOfBoundsException ex = new              IndexOutOfBoundsException(
					"    !index:" + index + ",size:" + size());
			//       
			throw ex;
		}

		String[] dest = new String[src.length - 1];
		System.arraycopy(src, 0, dest, 0, index);
		System.arraycopy(src, index + 1, dest, index, src.length - index - 1);

		src = dest;

	}

	//            
	public void insert(int index, E s) {
		//          ,            
		if (index < 0 || index >= src.length) {
			//       
			IndexOutOfBoundsException ex = new IndexOutOfBoundsException(
					"    !index:" + index + ",size:" + size());
			//       
			throw ex;
		}

		Object[] dest = new Object[src.length + 1];
		//     =index,         +1   
		System.arraycopy(src, index, dest, index + 1, src.length - index);

		dest[index] = s;

		src = dest;

	}

	//       
	public int size() {
		return src.length;
	}

}

 
    증분 길이 가 변 배열
 
 
public class MyList2 {

	private int rongliang;//     
	private int zengliang;//   
	private int num;//   【    】

	//          0        
	private Object[] src;

	public MyList2() {
		this(10, 10);
	}

	public MyList2(int rongliang) {
		this(rongliang, 10);
	}

	public MyList2(int rongliang, int zengliang) {
		this.rongliang = rongliang;
		this.zengliang = zengliang;
		src = new Object[rongliang];
	}

	//      Element
	public void add(E s) {
		//     >=    ,   
		if (num >= src.length) {
			//       
			Object[] dest = new Object[src.length + zengliang];
			//              
			System.arraycopy(src, 0, dest, 0, src.length);
			src = dest;
		}
		//      src      null   
		src[num++] = s;
	}

	//         
	public E get(int index) {
		if (index < 0 || index >= num) {
			throw new IndexOutOfBoundsException("    .index:" + index
					+ ",size:" + num);
		}
		return (E) src[index];
	}

	//                
	public void modify(int index, E s) {
		if (index < 0 || index >= num) {
			throw new IndexOutOfBoundsException("    .index:" + index
					+ ",size:" + num);
		}
		src[index] = s;
	}

	//          
	public void delete(int index) {
		if (index < 0 || index >= num) {
			throw new IndexOutOfBoundsException("    .index:" + index
					+ ",size:" + num);
		}
		System.arraycopy(src, index+1, src, index, num-index);
		num--;
		//       
		if(src.length-num>=zengliang){
			Object[] dest = new Object[src.length-zengliang];
			System.arraycopy(src, 0, dest, 0, num);
			src=dest;
		}
	}

	//            
	public void insert(int index, E s) {
		if (index < 0 || index >= num) {
			throw new IndexOutOfBoundsException("    .index:" + index
					+ ",size:" + num);
		}
		//     >=    ,   
		if (num >= src.length) {
			//       
			Object[] dest = new Object[src.length + zengliang];
			//              
			System.arraycopy(src, 0, dest, 0, src.length);
			src = dest;
		}
		//    >=index           
		System.arraycopy(src, index, src, index + 1, num - index);
		src[index] = s;
		num++;
	}

	//       
	public int size() {
		return num;
	}

}

 
   호출 배열
 
 
public class Demo {

	public static void main(String[] args) {
		//            
		MyList2 list = new MyList2(10,1000);
		
		list.add(10);
		list.add(20);
		list.add(30);
		list.add(40);
		list.add(50);
		
		list.delete(0);
		
		for(int i=0;i 
  

   

     

        , , , , , , , :

 

 

public class MyLinkList {

	//        0   ,      
	Node head = null;
	private Node last = null;
	private int num = 0;//     

	public void add(E e) {
		//         
		Node n = new Node(e);
		//           ,             
		if (head == null) {
			head = n;
		} else {
			//            ,                
			last.next = n;
		}
		last = n;
		num++;
	}

	//          
	public void insert(int index, E e) {
		if (index < 0 || index >= num) {
			throw new IndexOutOfBoundsException("    ,index:" + index
					+ ",size:" + num);
		}
		//      
		Node n = new Node(e);
		if (index == 0) {//  n       
			n.next = head;
			head = n;
		} else {
			//      index        index-1   
			Node n2 = getNode(index);
			Node n3 = getNode(index - 1);
			n3.next = n;
			n.next = n2;
		}
		num++;

	}

	public void delete(int index) {
		if (index < 0 || index >= num) {
			throw new IndexOutOfBoundsException("    ,index:" + index
					+ ",size:" + num);
		}
		if(index==0){
			Node n=head;
			head=head.next;
			n.next=null;
			n=null;
		}else{
			Node n1 = getNode(index-1);
			Node n = getNode(index);
			Node n2 = getNode(index+1);
			n1.next=n2;
			n.next=null;
		}
		num--;
	}

	public void modify(int index, E e) {
		if (index < 0 || index >= num) {
			throw new IndexOutOfBoundsException("    ,index:" + index
					+ ",size:" + num);
		}
		Node n = getNode(index);
		n.e = e;
	}

	//                 
	public E get(int index) {
		if (index < 0 || index >= num) {
			throw new IndexOutOfBoundsException("    ,index:" + index
					+ ",size:" + num);
		}
		Node n = getNode(index);
		return n.e;
	}

	//            
	private Node getNode(int index) {
		int t = 0;
		Node n = head;
		while (t < index) {
			n = n.next;
			t++;
		}
		return n;
	}

	//        
	public int size() {
		return num;
	}

	//               
	protected void getAllNode(Node n) {
		//           
		while (n != null) {
			E e = n.e;
			System.out.println(e);
			n = n.next;
		}
	}

	//      
	private class Node {
		E e;//       
		Node next;//         

		public Node(E e) {
			this.e = e;
		}
	}

}

 
   호출 링크
 
 
public class Demo {

	public static void main(String[] args) {
		
		MyLinkList list = new MyLinkList();
		
		list.add("AA");
		list.add("BB");
		list.add("CC");
		list.add("DD");
		
		list.modify(2, "FF");
		list.insert(4, "FF");
		list.delete(0);

		for(int i=0;i 
  

   

 

     , , , , , :

 

public class MyStack {

	//          0        
	Object[] src = new Object[0];

	//        
	public void push(E e) {
		Object[] dest = new Object[src.length + 1];
		//              
		System.arraycopy(src, 0, dest, 0, src.length);
		//                 
		dest[src.length] = e;
		//  src     
		src = dest;
	}

	//        
	public E get() {
		//               
		E e = (E) src[src.length - 1];
		return e;
	}

	//        
	public E poll() {
		//               
		E e = (E) src[src.length - 1];
		//                -1
		Object[] dest = new Object[src.length - 1];
		//                      
		System.arraycopy(src, 0, dest, 0, dest.length);
		//  src     
		src = dest;
		return e;
	}

	//        
	public boolean isEmpty() {
		return src.length == 0;
	}

}

 
 
 링크 를 이용 하여 스 택 을 실현 하 다.
 
public class MyStackLink {

	//        0   
	Node head = null;
	int length;//     

	//        
	public void push(E e) {
		//       
		Node n = new Node(e);
		//                
		n.next = head;
		head = n;
		length++;
	}

	//        
	public E get() {
		return head == null ? null : head.e;
	}

	//        
	public E poll() {
		if (head == null) {
			return null;
		}
		//        ,         
		Node n = head;
		head = n.next;
		n.next = null;
		length--;
		return n.e;
	}

	//       
	public boolean isEmpty() {
		return length == 0;
	}

	//         
	private class Node {
		E e;
		Node next;

		public Node(E e) {
			this.e = e;
		}

	}

}

    
 
호출 스 택:
public class Demo {
	
	public static void main(String[] args) {
		
//		MyStackLink stack = new MyStackLink();
		
		
		Stack stack = new Stack();
		
		//      
		stack.push("AA");
		stack.push("BB");
		stack.push("CC");
		stack.push("DD");
		
		
		while(!stack.isEmpty()){
			String s = stack.pop();
			System.out.println(s);
			
		}
		
		
		//       
    	String s = stack.get();
		System.out.println(s);	
		//       
		String s1 = stack.poll();
		System.out.println(s1);
		
		s = stack.get();
		System.out.println(s);
	}

}

 
 
 

좋은 웹페이지 즐겨찾기