순차 리스트

순차 리스트

---

순차 리스트

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

설명

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

추상 자료형 (ADT)

자료형	반환값	내용
initialize()	void	리스트 초기화
insert(Object data)	boolean	리스트에 데이터 저장
first()	Object	첫 번째 데이터를 가리키도록 하며 값을 반환
next()	Object	현재 참조하고 있는 데이터의 다음 데이터를 가리키도록 하며 값을 반환
remove()	Object	현재 참조하고 있는 데이터를 지움
count()	int	리스트에 저장된 데이터의 개수를 반환

구현

 

• 디렉토리 구조
  

  

• 인터페이스 구현
  다형성을 위해 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);
          }
      }
  }