순차 자료구조와 선형 리스트

순차 자료구조

순차 자료구조란?

• 구현할 자료들을 논리적인 순서대로 메모리에 연속하여 저장하는 구현 방식
• 순차적으로 저장한다는 것은 배열을 이용하여 구현한다는 의미로 이해하면 편하다.

순차 자료구조의 특징

• 메모리 저장 방식
  • 메모리의 시작 위치부터 빈자리 없이 자료를 순서대로 연속하여 저장한다.
  • 논리적인 순서와 물리적인 순서가 일치하는 구현 방식
• 연산 특징
  • 삽입·삭제 연산을 해도 빈자리 없이 자료가 순서대로 연속하여 저장된다.
  • 변경된 논리적인 순서와 저장된 물리적인 순서가 일치한다.
• 프로그램 기법
  • 배열을 이용한 구현

선형 리스트 (Linear List)

선형 리스트란?

• 원소들을 순서대로 나열한 목록
• 순서 리스트(Order List)라고도 부른다.
• 메모리에 저장하는 구현 방식에 따라서 분류한다.
  • 순차 방식
    • 선형 순차 리스트 (Linear Sequential List)
    • 일반적으로 선형 리스트라고 부른다.
  • 연결 방식
    • 선형 연결 리스트 (Linear Linked List)
    • 일반적으로 연결 리스트라고 부른다.

선형 순차 리스트의 특징

• 원소들이 나열된 논리적인 순서와 메모리에 저장되는 물리적인 순서가 동일하다.
• 원소들이 순서대로 연속하여 저장되기 때문에 시작 위치와 원소 크기를 알면 특정 원소의 위치를 구하기 쉽다.
  • 시작 위치가 a고, 원소 크기가 s일 경우 n번째 원소의 위치는 a + (n - 1) * s가 된다.

리스트 표현 방식

• 요소가 있는 경우
  • 리스트 이름 = (원소 1, 원소 2, ..., 원소 n)
• 요소가 없는 경우
  • 리스트 이름 = ()
  • 공백 리스트라고 부른다.

원소의 삽입

• 만약 순서대로 a, b, c, d, e가 나열되있다고 가정했을 때 f를 c와 d 사이에 삽입하게 되면 몇 번의 이동이 발생할까?
  1. a ~ e까지 1 ~ 5의 숫자에 매핑했을 때 f는 3과 4 사이에 끼어들게 된다.
  2. 그렇다면 d와 e는 한 자리씩 밀려나게 된다.
  3. 발생한 일만 봤을 때는 한 자리씩 1번 밀려난 것 같이 보일 수도 있다.
  4. 그러나 실제로는 d와 e가 각각 1번씩 밀려난 것이다.
  5. 이를 수식으로 만들기 위해 파악을 해보면
     기존에는 5개의 원소가 존재했으며,
     새로운 요소를 4번의 위치에 추가하고자 하였으며,
     실제로 이동이 발생한 횟수는 2회라는 결과가 나왔다.
  6. 이를 바탕으로 계산했을 때 수식은 아래와 같다.
  • 2 (이동 횟수) = 6 (기존 원소의 개수 5개 + 새로 추가하려는 원소 1개) - 4 (삽입하려는 위치의 번호)
    1. 6번의 수식에서 새로 추가하려는 원소 1개라고 적혀있긴 하지만 원소는 1개씩 추가되기 때문에 1로 치환한다.
    2. 즉, 정리된 수식은 아래와 같다.
  • 이동 횟수 = 기존 원소의 개수 + 1 - 삽입하려는 위치의 번호
    1. 그런데 8번의 수식은 현실 세계의 기준이고 컴퓨터 상에서 사용되는 기준이 아니다.
       컴퓨터 상의 기준으로 변경하면 최종적으로 다음과 같이 바뀐다.
  • 이동 횟수 = 마지막 원소의 인덱스 + 1 - 삽입하려는 위치의 인덱스

원소의 삭제

• 만약 순서대로 a, b, c, d, e가 나열되있다고 가정했을 때 c가 삭제된다면 몇 번의 이동이 발생할까?
  1. a ~ e까지 1 ~ 5의 숫자에 매핑했을 때 c는 3번의 위치에 있다.
  2. c가 삭제된다면 d와 e는 각각 한 자리씩 앞으로 당겨져서 총 2회의 이동이 발생한다.
  3. 이를 바탕으로 게산했을 때 수식은 아래와 같다.
  • 2 (이동 횟수) = 5 (기존 원소의 개수 5개) - 3 (삭제한 원소의 위치)
    1. 그런데 3번의 수식은 현실 세계의 기준이고 컴퓨터 상에서 사용되는 기준이 아니다.
       컴퓨터 상의 기준으로 변경하면 최종적으로 다음과 같이 바뀐다.
  • 이동 횟수 = 마지막 원소의 인덱스 - 삭제한 원소의 인덱스

구현하기

• Java에서는 선현 리스트를 구현하는 2가지 방법이 있다.
  • Array (배열)
  • ArrayList
• 공통점
  • 연속된 메모리 공간에 데이터를 저장한다.
• 차이점
  • 배열
    • 초기화 시 리스트의 크기가 고정된다.
    • 초기화시 메모리에 할당한다.
      • ArrayList보다 속도가 빠르다.
    • 사이즈를 변경할 수 없다.
  • ArrayList
    • 리스트의 크기를 정의하지 않으며 크기가 가변적이다.
    • 데이터 추가 삭제시 메모리를 재할당한다.
      • Array보다 속도가 느리다.
    • 데이터의 추가 및 삭제가 가능하다.