개발자로 살아남기

순차 리스트

순차 리스트

• 데이터가 메모리에 연속적으로 저장됨 (ex. 배열 등)
• 장점
  1) 인덱스로 데이터에 접근할 수 있으므로 속도가 빠름
• 단점
  1) 배열의 길이가 사전에 정의되어야 함
  2) 중간 데이터 삭제 시 해당 인덱스 이후의 값들은 한 칸씩 이동이 발생

설명

• 삽입
  - 보통 배열의 마지막에 데이터가 삽입되며, 삽입 시 배열의 크기도 고려해야 함
  - 배열의 중간에 데이터를 삽입하기 위해서는 배열의 길이가 충분한지 확인해야 하며, 삽입된 위치 뒤에 존재하는 모든 데이터들이 한 칸씩 뒤로 이동해야 하므로 중간에 데이터 삽입 시 비효율적
  - 시간 복잡도 : O(n)
  
  
• 삭제
  - 배열의 중간에 위치한 데이터를 삭제할 경우 해당 위치의 뒤 데이터들은 한 칸씩 앞으로 이동해야 하므로 배열의 크기가 크고 삭제가 빈번할수록 비효율적
  - 시간복잡도 : O(n)
  
  
• 조회(검색)
  - 배열에 존재하는 데이터에 대한 인덱스 값들이 고정되어 있기 때문에 조회가 간편함
  - 시간복잡도 : O(n) [찾으려는 값이 없을 경우]
  
  
• 접근
  - 배열의 인덱스로 데이터에 바로 접근할 수 있음
  - 시간복잡도 : O(1)
  
  

추상 자료형 (ADT)

구현

• 디렉토리 구조
  

  

• 인터페이스 구현
  다형성을 위해 List관련 메소드를 인터페이스로 구현

  package List;
  
  // 다형성을 위해 List를 인터페이스로 생성
  public interface List {
      // 리스트 초기화
      void initialize();
      // 리스트에 데이터 삽입 (어떤 값이 올 지 모르므로 Object를 인자로 받음)
      boolean insert(Object data);
      // 첫 번째 데이터를 가리키도록 하며 값을 반환
      Object first();
      // 현재 참조하고 있는 데이터의 다음 데이터를 가리키도록 하며 값을 반환
      Object next();
      // 현재 참조하고 있는 데이터를 지움
      Object remove();
      // 리스트에 저장된 데이터의 개수를 반환
      int count();
  }

• 순차 리스트 구현
  실제 리스트 코드 작성
  

  package List.ArrayList;
  import List.List;
  
  public class ArrayList implements List {
      // 리스트 최대 개수를 10으로 지정
      final int MAX_LIST_COUNT = 10;
      Object[] list = new Object[MAX_LIST_COUNT];
      // 현재 위치 저장 변수 (아무것도 참조하고 있지 않으므로 -1)
      int curPosition = -1;
      // 리스트에 저장된 데이터 개수
      int countOfData = 0;
  
      @Override
      public void initialize() {
          curPosition = -1;
          countOfData = 0;
          for(int i=0; i<MAX_LIST_COUNT; i++){
              list[i] = null;
          }
      }
  
      @Override
      public boolean insert(Object data) {
          if (data == null){
              System.out.println("null 값을 추가할 수 없습니다.");
              return false;
          }
  
          if (countOfData >= 100){
              System.out.println("더이상 데이터를 추가할 수 없습니다.");
              return false;
          }
  
          // 리스트에 데이터 저장
          list[countOfData++] = data;
          return true;
      }
  
      @Override
      public Object first() {
          if (countOfData == 0){
              System.out.println("데이터가 없습니다.");
              return null;
          }
  
          // 첫 번째를 가리키도록 설정
          curPosition = 0;
          // 첫 번째 데이터 반환
          return list[curPosition];
      }
  
      @Override
      public Object next() {
          if (curPosition >= countOfData - 1){
              System.out.println("데이터가 없습니다.");
              return null;
          }
  
          curPosition++;
          return list[curPosition];
      }
  
      @Override
      public Object remove() {
          if (countOfData == 0){
              System.out.println("데이터가 없습니다.");
              return null;
          }
  
          // 현재 참조된 데이터를 제거하기 위해 변수에 할당
          Object rData = list[curPosition];
          // 한 칸씩 당기기 위한 반복문
          for(int i=curPosition; i<countOfData - 1; i++){
              list[i] = list[i+1];
          }
  
          // 데이터가 제거됐으므로 개수와 위치를 하나씩 감소
          countOfData--;
          curPosition--;
          return rData;
      }
  
      @Override
      public int count() {
          return countOfData;
      }
  }

  
  
• 메인 구현
  데이터 삽입, 삭제 및 조회 기능 테스트
  

  package List.ArrayList;
  
  public class Main {
      public static void main(String[] args) {
          ArrayList list = new ArrayList();
  
          // 리스트 초기화
          list.initialize();
  
          // 리스트 데이터 추가
          list.insert(1); list.insert(2);
          list.insert(3); list.insert(4);
          list.insert(5); list.insert(6);
  
          // 첫 번째 인덱스를 가리키도록 설정
          Object data = list.first();
          System.out.println(data);
          // data가 null이 아닐때까지 반복
          while((data = list.next()) != null){
              System.out.println(data);
          }
  
          // data 삭제
          Object rData = null;
          data = list.first();
          if ((int)data == 4){
              rData = list.remove();
              System.out.println(rData + " 데이터가 삭제되었습니다.");
              rData = null;
          }
          while((data = list.next()) != null){
              if ((int)data == 4){
                  rData = list.remove();
                  System.out.println(rData + " 데이터가 삭제되었습니다.");
                  rData = null;
              }
          }
  
          // 삭제 후 재출력
          data = list.first();
          System.out.println(data);
          // data가 null이 아닐때까지 반복
          while((data = list.next()) != null){
              System.out.println(data);
          }
      }
  }