자바 단일 체인 테이블 구현

실현 해 야 할 방법: 인터페이스:

public interface MyList {
 /**      **/
 void add(Object element);
 /**      **/
 void remove(Object element);
 /**        **/
 void delete(int index);
 /*
  *              
  * index
  * newElement
  */
 void update(int index,Object newElement);
 /*
  *         target    
  */
 boolean contains(Object target);
 /*
  *        
  */
 Object indexOf(int index);
}

Array List: 말 그대로 배열 로 이 루어 집 니 다. 코드 는 다음 과 같 습 니 다. add (): 요 소 를 추가 하고 배열 에 대한 할당 을 통 해 경 계 를 넘 거나 더 큰 배열 로 가면 원래 의 데 이 터 를 새로운 배열 reove () 로 복사 합 니 다. 이 위치의 요 소 를 삭제 하고 뒤의 요 소 를 앞으로 이동 합 니 다.

import java.util.Arrays;
/*
 *    (  )       
 */
public class MyArrayList implements MyList {
 private Object[]elements;//            
 private int size;//      
 private int capacity=10;//  
 public MyArrayList(int capacity) {
  this.capacity=capacity;
  elements =new Object[capacity];
 } 
 public MyArrayList(){
 elements =new Object[capacity];
 }
 @Override
 public void add(Object element) {//  
  // TODO          
  if(size==capacity) {//  
   capacity*=2;
   Object newArray[]=new Object[capacity];
   for(int i=0;i<size;i++) {
    newArray[i]=elements[i];
   }
   elements=newArray;
  }
  elements[size++]=element;
 }
 @Override
 public void remove(Object element) {
  // TODO          
  for(int i=0;i<size;i++) {
   if(elements[i]==element) {
    delete(i);
    break;
   }
  }
 }
 @Override
 public void delete(int index) {
  // TODO          
  for(int i=index;i<size-1;i++) {
   elements[i]=elements[i+1];
  }
  elements[size-1]=null;
  size--;
 }
 @Override
 public void update(int index, Object newElement) {
  // TODO          
  elements[index]=newElement;
 }
 @Override
 public boolean contains(Object target) {
  // TODO          
  for(int i=0;i<size;i++) {
   if(elements[i]==target)return true;
  }
  return false;
 }
 @Override
 public Object indexOf(int index) {
  // TODO          
  return elements[index];
 }
 //@Override
 public String toString() {
  StringBuilder str=new StringBuilder();
  for(int i=0;i<capacity;i++) {
   if(elements[i]==null)break;
   else if(i==0)str.append(elements[i]);
   else str.append(","+elements[i]);
  }  
  return "["+str+"]";
 }
 
}

LinkedList: 노드 를 통 해 노드 클래스 를 실현 합 니 다.

package     ;
/*  */
public class ListNode {
 Object data;
 ListNode next;
 public ListNode(Object data) {
  this.data=data;
 }
}

노드 마다 두 개의 값 이 있 습 니 다. 하 나 는 현재 값 을 대표 합 니 다. 하 나 는 다음 Node add () 를 가리 킵 니 다. 새로운 Node 를 얻 고 이전 노드 의 지침 이 이 Node remove () 를 가리 키 도록 합 니 다. 삭제 해 야 할 노드 를 찾 아 이전 노드 의 지침 이 이 노드 의 다음 노드 (원래 노드 가 삭제 되 지 않 았 음) 를 가리 키 도록 합 니 다.

public class SingleLinkedList implements MyList{
 private ListNode first;
 private ListNode last;
 private int size;
 @Override
 public void add(Object element) {
  // TODO          
  if(first==null) {
   first=new ListNode(element);
   last=first;
  }else {
   last.next =new ListNode(element);
   last=last.next;
  }
  size++;
 }
 @Override
 public void remove(Object element) {
  // TODO          
  ListNode p=first;
  ListNode pre =null;
  while(p!=null) {
   if(p.data.equals(element)) {
    if(p==first)first=first.next;//     
    else pre.next=p.next; 
    break;//    ，           
   }
   pre=p;
   p=p.next;
  }
 }
 @Override
 public void delete(int index) {
  // TODO          
  int i=0;//       
  ListNode p=first;
  ListNode pre=null;
  while(p!=null) {
   if(i==index) {
    if(p==first)first=first.next;
    else pre.next=p.next;
    break;
   }
   p=p.next;
   i++;
  }
  size--;
 }
 @Override
 public void update(int index, Object newElement) {
  // TODO          
  if(index<0||index>size)return;
  int i=0;//       
  ListNode p=first;
  ListNode pre=null;
  while(p!=null) {
   if(i==index) {
    p.data=newElement;
    break;
   }
   p=p.next;
   i++;
  }
 }
 @Override
 public boolean contains(Object target) {
  // TODO          
  ListNode p=first;
  ListNode pre =null;
  while(p!=null) {
   if(p.data.equals(target)) {
    return true;
   }
   pre=p;
   p=p.next;
  }
  return false;
 }
 @Override
 public Object indexOf(int index) {
  // TODO          
  int i=0;//       
  ListNode p=first;
  ListNode pre=null;
  while(p!=null) {
   if(i==index) {
    return p.data;
   }
   p=p.next;
   i++;
  }
  return null;
 }
 @Override
 public String toString() {
  StringBuilder sb=new StringBuilder("[");
  ListNode p=first;
  while(p!=null) {
   if(p.next==null)sb.append(p.data);
   else sb.append(p.data).append(",");
   p=p.next;
  }
  sb.append("]");
  return sb.toString();
 }
}