IntLinkedBag 클래스

코드 설명

/******************************************************************************
* IntLinkedBag은 int 숫자들의 컬렉션입니다.
*
* @note
*   (1) 요소 수가 Int.MAX_VALUE를 초과하면 countOccurrences, 
*   size, grab 메서드의 결과가 올바르지 않을 수 있습니다.
*   <p>
*   (2) 이 클래스의 선형 알고리즘들은 느리므로, 많은 요소를 담는 경우
*   성능이 좋지 않습니다.
*
******************************************************************************/
public class IntLinkedBag implements Cloneable
{
   // IntLinkedBag 클래스의 불변 조건:
   //   1. 이 가방의 요소들은 연결 리스트로 저장됩니다.
   //   2. 리스트의 첫 번째 노드는 head 인스턴스 변수에 저장됩니다.
   //   3. 리스트의 전체 요소 수는 manyNodes 인스턴스 변수에 저장됩니다.
   private IntNode head;
   private int manyNodes;   


   /**
   * 빈 가방을 초기화합니다.
   * @param - 없음
   * @postcondition
   *   이 가방은 비어 있습니다.
   **/
   public IntLinkedBag( )
   {
      head = null;
      manyNodes = 0;
   }
        
 
   /**
   * 새로운 요소를 가방에 추가합니다.
   * @param element
   *   추가할 새로운 요소
   * @postcondition
   *   요소의 복사본이 가방에 추가됩니다.
   * @exception OutOfMemoryError
   *   새로운 IntNode를 생성할 메모리가 부족한 경우
   **/
   public void add(int element)
   {      
      head = new IntNode(element, head);
      manyNodes++;
   }


   /**
   * 다른 가방의 내용을 이 가방에 추가합니다.
   * @param addend
   *   이 가방에 추가될 요소들을 가진 가방
   * @precondition
   *   매개변수 addend는 null이 아니어야 합니다.
   * @postcondition
   *   addend의 요소들이 이 가방에 추가됩니다.
   * @exception NullPointerException
   *   addend가 null인 경우
   * @exception OutOfMemoryError
   *   가방의 크기를 늘릴 메모리가 부족한 경우
   **/
   public void addAll(IntLinkedBag addend)
   {
      IntNode[] copyInfo;

      if (addend.manyNodes > 0)
      {
         copyInfo = IntNode.listCopyWithTail(addend.head);
         copyInfo[1].setLink(head); // 복사된 리스트의 꼬리를 내 head에 연결
         head = copyInfo[0];        // head를 복사된 리스트의 head로 설정
         manyNodes += addend.manyNodes;
      }
   }

     
   /**
   * 여러 개의 새로운 요소들을 이 가방에 추가합니다.
   * @param elements
   *   (가변 인자)
   *   삽입될 하나 이상의 요소들
   * @postcondition
   *   각 요소의 복사본이 이 가방에 추가됩니다.
   * @exception OutOfMemoryError
   *   가방의 크기를 늘릴 메모리가 부족한 경우
   **/
   public void addMany(int... elements)
   {
      for (int i : elements)
         add(i); 	       
   }

     
   /**
   * 이 가방의 복사본을 생성합니다.
   * @param - 없음
   * @return
   *   이 가방의 복사본을 반환합니다. 복사본과 원본은 이후의 변경에 영향을 미치지 않습니다.
   * @exception OutOfMemoryError
   *   복사를 위한 메모리가 부족한 경우
   **/ 
   public Object clone()
   {
      IntLinkedBag answer;

      try
      {
         answer = (IntLinkedBag) super.clone();
      }
      catch (CloneNotSupportedException e)
      {
         throw new RuntimeException("이 클래스는 Cloneable을 구현하지 않았습니다.");
      }

      answer.head = IntNode.listCopy(head);
      return answer;
   }
   

   /**
   * 특정 요소가 이 가방에 몇 번 포함되어 있는지 확인합니다.
   * @param target
   *   개수를 셀 요소
   * @return
   *   target이 가방에 존재하는 횟수
   **/
   public int countOccurrences(int target)
   {
      int answer = 0;
      IntNode cursor = IntNode.listSearch(head, target);

      while (cursor != null)
      {
         answer++;
         cursor = cursor.getLink();
         cursor = IntNode.listSearch(cursor, target);
      }
      return answer;
   }

    
   /**
   * 이 가방에서 임의의 요소를 반환합니다.
   * @param - 없음
   * @precondition
   *   가방이 비어 있지 않아야 합니다.
   * @return
   *   가방에서 임의로 선택된 요소 하나
   * @exception IllegalStateException
   *   가방이 비어 있는 경우
   **/
   public int grab()
   {
      if (manyNodes == 0)
         throw new IllegalStateException("가방이 비어 있습니다.");

      int i = (int)(Math.random() * manyNodes) + 1;
      IntNode cursor = IntNode.listPosition(head, i);
      return cursor.getData();
   }
   
             
   /**
   * 지정된 요소를 가방에서 하나 제거합니다.
   * @param target
   *   제거할 요소
   * @postcondition
   *   target이 가방에 존재하면 하나가 제거되고 true를 반환합니다.
   *   존재하지 않으면 가방은 변경되지 않고 false를 반환합니다.
   **/
   public boolean remove(int target)
   {
      IntNode targetNode = IntNode.listSearch(head, target);

      if (targetNode == null)
         return false;
      else
      {
         targetNode.setData(head.getData());
         head = head.getLink();
         manyNodes--;
         return true;
      }
   }
        
      
   /**
   * 이 가방에 있는 요소의 개수를 반환합니다.
   * @param - 없음
   * @return
   *   이 가방에 있는 전체 요소 수
   **/                           
   public int size()
   {
      return manyNodes;
   }
   

   /**
   * 두 가방의 요소를 모두 포함하는 새 가방을 생성합니다.
   * @param b1
   *   첫 번째 가방
   * @param b2
   *   두 번째 가방
   * @precondition
   *   b1과 b2는 null이 아니어야 합니다.
   * @return
   *   b1과 b2의 합집합을 담는 새 가방
   * @exception IllegalArgumentException
   *   하나라도 null인 경우
   * @exception OutOfMemoryError
   *   새 가방 생성을 위한 메모리가 부족한 경우
   **/   
   public static IntLinkedBag union(IntLinkedBag b1, IntLinkedBag b2)
   {       
      IntLinkedBag answer = new IntLinkedBag();

      answer.addAll(b1);
      answer.addAll(b2);     
      return answer;
   }
}

• IntLinkedBag은 int 형 정수 데이터를 연결 리스트로 저장하는 가방의 자료구조이다.
• 요소들의 순서는 중요하지 않고, 중복 요소를 허용한다.
• 내부적으로 IntNode 클래스를 활용한다.

인스턴스 변수

private IntNode head;
private int manyNodes;

• head: 연결 리스트의 첫 번째 노드 참조
• manyItems: 가방에 들어 있는 전체 요소의 수

생성자

public IntLinkedBag()

head = null;
manyNodes = 0;

• 빈 가방을 초기화해 준다.
• 연결 리스트가 비어있음을 나타낸다.

메서드

public void add(int element)

head = new IntNode(element, head);
manyNodes++;

• head 앞에 새로운 노드를 추가해 준다.
• 연결 리스트는 앞에서부터 삽입된다.

public void addAll(IntLinkedBag addend)

copyInfo = IntNode.listCopyWithTail(addend.head);
copyInfo[1].setLink(head);
head = copyInfo[0];
manyNodes += addend.manyNodes;

• addend의 연결 리스트를 복사해서 head 앞에 연결한다. (깊은 복사)
• 꼬리(tail)는 현제 head와 연결해 준다.

public void addMany(int... elements)

• 가변인자를 활용하는 여러 요소를 한 번에 추가한다.

for (int i : elements)
    add(i);

• add()를 반복적으로 호출한다.
• 맨 앞부터 삽입되므로 결과적으로 마지막 요소가 가장 앞에 위치한다.

public Object clone()

• 복사본을 반환해 준다.

answer = (IntLinkedBag) super.clone();
answer.head = IntNode.listCopy(head);

• super.clone의 얕은 복사를 실행해 준다.
• 이후에 IntNode.listCopy(head)로 연결 리스트 전체를 깊은 복사 수행해 준다.

public int countOccurrences(int target)

• target값이 몇 번 등장하였는지 개수를 세준다.

IntNode cursor = IntNode.listSearch(head, target);
while (cursor != null) {
    answer++;
    cursor = cursor.getLink();
    cursor = IntNode.listSearch(cursor, target);
}

• listSearch()로 target값이 있는 노드를 찾는다.
• 찾은 노드 이후부터 다시 찾아준다.
• 중복된 값들은 모두 카운트해준다.

public int grab()

• 가방의 임의의 요소 하나를 반환해 준다.

int i = (int)(Math.random() * manyNodes) + 1;
IntNode cursor = IntNode.listPosition(head, i);
return cursor.getData();

• 전체 개수 내에서 무작위 인덱스를 선택해 준다.
• 해당 인덱스 위치의 데이터를 반환해 준다.

public boolean remove(int target)

• 특정 요소 하나만 제거한다.

IntNode targetNode = IntNode.listSearch(head, target);
if (targetNode == null) return false;

targetNode.setData(head.getData());
head = head.getLink();
manyNodes--;
return true;

• 찾은 노드의 데이터를 head의 데이터로 덮어쓴다.
• head를 다음 노드로 옮긴다.
• 리스트 순서가 중요하지 않기 때문에 가능한 기법이다.

public int size()

• 현제 가방에 저장된 요소 개수 반환해 준다.
• manyNodes값만 리턴해주면 된다.

public static IntLinkedBag union(IntLinkedBag b1, IntLinkedBag b2)

• 두 가방의 요소를 모두 포함하는 새로운 가방을 반환해 준다.

IntLinkedBag answer = new IntLinkedBag();
answer.addAll(b1);
answer.addAll(b2);
return answer;

• b1, b2를 모두 깊은 복사되어 answer에 병합된다.
• 순서는 중요하지 않기 때문에 어떤 순서로 addAll을 호출해도 상관없다.

실행 예제

public class IntLinkedBagTest {
    public static void main(String[] args) {
        // 1. 빈 가방 생성
        IntLinkedBag bag1 = new IntLinkedBag();
        System.out.println("새로운 빈 가방 생성. 크기: " + bag1.size());

        // 2. 요소 추가
        bag1.add(10);
        bag1.add(20);
        bag1.add(10);
        System.out.println("10, 20, 10 추가 후 크기: " + bag1.size()); // 3

        // 3. 요소 개수 세기
        System.out.println("10의 개수: " + bag1.countOccurrences(10)); // 2
        System.out.println("20의 개수: " + bag1.countOccurrences(20)); // 1
        System.out.println("30의 개수: " + bag1.countOccurrences(30)); // 0

        // 4. grab(): 랜덤 요소 뽑기
        System.out.println("랜덤 grab: " + bag1.grab());

        // 5. 요소 제거
        boolean removed = bag1.remove(10);
        System.out.println("10 제거됨?: " + removed);
        System.out.println("10 제거 후 개수: " + bag1.countOccurrences(10));
        System.out.println("현재 가방 크기: " + bag1.size());

        // 6. 복수 요소 추가
        bag1.addMany(50, 60, 70);
        System.out.println("50, 60, 70 추가 후 크기: " + bag1.size());

        // 7. 다른 가방 만들고 addAll로 병합
        IntLinkedBag bag2 = new IntLinkedBag();
        bag2.add(100);
        bag2.add(200);
        bag1.addAll(bag2);
        System.out.println("bag2 병합 후 bag1 크기: " + bag1.size());

        // 8. 복제 테스트
        IntLinkedBag bag3 = (IntLinkedBag) bag1.clone();
        System.out.println("bag1 복제 -> bag3 생성. 크기: " + bag3.size());

        // 9. union 사용해 두 가방 합치기
        IntLinkedBag mergedBag = IntLinkedBag.union(bag1, bag2);
        System.out.println("bag1 + bag2 합집합 bag 생성. 크기: " + mergedBag.size());

        // 10. 빈 가방에서 grab 시도 (예외 발생 테스트)
        try {
            IntLinkedBag emptyBag = new IntLinkedBag();
            emptyBag.grab(); // 예외 발생
        } catch (IllegalStateException e) {
            System.out.println("빈 가방에서 grab -> 예외 발생: " + e.getMessage());
        }
    }
}