[자료구조] 선형구조

자료구조(1) - 선형구조

효율적인 작업처리를 위해서 상황에 따라 적절한 자료구조를 취사선택해서 사용해야한다.

 

배열

• Array

  • 대부분의 프로그래밍 언어에서 사용 가능한 가장 기본적인 자료구조로, 번호(index)와 번호에 대응하는 서로 연관된 데이터로 이루어진다.
  • 데이터의 순서가 있으며 중복을 허용한다.
  • index는 int 혹은 long형이다.
  • 배열은 선언과 동시에 길이를 지정한다. 그리고 그 길이는 변경 불가능하다. type[] arr = new type[n]; type[] arr = {value1, value2, ...}; type[][] arr = new type[n][m]; type[][] arr = {{value1-1, value1-2, ...}, {value2-1, value2-2, ...}}; 와 같은 꼴로 선언한다.
  • 선언과 동시에 값을 넣어서 초기화해주면 각각의 값이 배열에 0번부터 순서대로 들어가고, 배열의 크기만 선언 해 줄 경우 배열 내 모든 값이 0(int), 0.0(double), 0.0f(float), false(boolean), ''(char), null(String) 값으로 초기화되며, 초기화 시 값이 지정되지 않은 배열도 마찬가지로 적용된다.

• 장점

  • 하나의 이름으로 여러 데이터를 보관 및 관리할 수 있고, 고정된 인덱스 값을 이용해 빠르게 원하는 값을 찾을 수 있다.
  • 데이터를 원하는 순서대로 입력해 나열할 수 있다.
  • 반복문을 이용하면 쉽게 값을 순차적으로 넣고, 꺼낼 수 있다.

• 단점

  • 데이터가 빈 값인 인덱스가 존재하거나 기존의 데이터가 삭제되어도 배열의 길이는 변하지 않아 메모리가 낭비될 수 있다.

    • 가변배열을 만드는 경우 새로운 배열을 할당 후 값을 복사한 뒤 기존배열을 삭제하는 과정을 거치므로 자원낭비가 크다.
    • 이러한 한계를 해결하기 위해서 list를 사용한다.

  • 이미 입력된 배열의 순서를 바꾸는 것이 어렵다.

 

리스트

• List

  • 배열의 장점인 고정된 index를 사용하지 못하는 대신 빈 공간이 없이 데이터 적재가 가능한 자료구조이다.
  • 데이터의 순서가 있으며 중복이 허용된다.
  • 배열의 번호(index)대신 순서(sequence)를 사용하며, 빈 값은 허용되지 않는다.
  • index는 데이터가 저장된 곳의 주소값이지만, sequence는 단지 리스트에서 몇번째에 위치하는 데이터인지만 나타낸다.

• ArrayList

  • 필요에 따라 크기를 변화시킬 수 있는 가변크기배열이다.
  • LinkedList와 사용법과 실행 결과가 거의 같지만 내부적인 구현 방법이 다르다.
  • ArrayList는 내부적으로 데이터를 배열에 저장하므로 정확한 위치값을 알 수 있어 접근은 빠르지만 데이터의 추가/삭제가 느리다.

• LinkedList

  • 노드(Node)와 링크(Link)로 구성된다. 노드와 노드의 연결을 이용해서 리스트를 구현한 것이다.
  • 노드는 실제 정보를 담고 있는 하나의 단위이며, 링크는 노드 간 위치정보를 저장하고 있어 연결리스트의 순서를 유지할 수 있다.
  • 제일 앞 노드를 head라고 한다.
  • 배열이나 ArrayList와 다르게 위치가 흩어져있기 때문에 맨 앞 노드부터 링크를 타고 항목순회를 해야하므로 비효율적이지만, 추가/삭제 시에는 추가할 데이터의 이전, 이후 노드의 참조값(다음값)만 변경하면 되기때문에 데이터 변경이 빠르다.
  • 조회가 많을 경우 ArrayList가 더 효율적이며, 데이터의 추가 및 삭제가 더 많을 경우 LinkedList가 더 빠르다.

• 장점

  • 데이터를 중간 위치로 추가/삭제하기 편하다. (list.add(value); list.remove(seq);)
  • 크기를 유동적으로 변경할 수 있다.
  • 순차적으로 접근 가능하다.

• 단점

  • 자료의 양이 많이 있을 경우 효율성이 떨어진다.
  • 랜덤으로 액세스하기에 불리하다.
  • 검색이 느리다.

 

스택

• Stack

  • 삽입 및 삭제가 한 쪽 끝에서만 발생하는 후입선출(Last In First Out) 방식 자료구조이다. (뽑아쓰는 종이컵을 생각해보자.)
  • Top : 스택 구조의 가장 윗 부분(마지막 부분)으로, 자료의 삽입과 삭제가 이루어지는 부분이다. 초기값은 -1이다.
  • Bottom : 스택의 맨 아랫부분을 가리킨다.
  • push 시 기존 Top 포인트의 위에 데이터를 넣고, 넣어진 데이터의 위치가 Top이 된다.
  • pop을 하면 현재 Top 위치의 데이터를 꺼낸다. 해당 데이터는 스택에서 삭제되며 바로 아래의 데이터가 Top이 된다.
  • peek을 하면 현재 Top 위치에 있는 데이터를 삭제하지 않고 꺼낼 수 있다.
  • isEmpty 혹은 isFull을 이용해서 스택이 비거나 가득찼는지 체크할 수 있다.
  • 스택이 비어있는데 pop을 할 경우 Stack Underflow가 발생하고, 스택이 꽉 차있는데 push를 할 경우 Stack Overflow가 발생한다. 이를 대비한 예외처리를 해주어야한다.

 

큐

• Queue

  • 한쪽 끝에서 자료가 삽입 되고 반대쪽 끝에서 자료가 삭제되는 선입선출(First In First Out) 방식의 자료구조이다.
  • Rear는 삽입이 발생하는 부분으로 가장 마지막 데이터의 위치이다.
  • Front는 삭제가 발생하는 부분으로 제일 앞에 있는 데이터의 위치이다.
  • 선형큐를 사용하면 삭제가 발생할 때 마다 맨 앞의 데이터를 삭제하고 나머지 데이터를 한 칸씩 당겨주는 작업이 필요하기 때문에 작업에 많은 시간이 걸리며, 큐의 삭제가 계속 될 경우 마지막 배열에 도달했을 때 실제로는 데이터 공간이 남아있지만 오버플로가 발생하게 된다.
  • 이러한 단점을 보완하기 위해서 원형 큐(환형 큐)나 링크드 큐를 사용한다.
  • 원형 큐는 큐의 첫 번째 원소와 마지막 원소가 서로 연결되어 있는 형태로, Front가 큐의 끝에 닿으면 큐의 맨 앞으로 자료를 보내 원형으로 연결 하는 방식이다. (queue[n-1] -> queue[0])
  • 링크드 큐는 연결 리스트로 구현한 큐로, 각 노드는 다음 노드를 가리킨다. 큐의 길이를 쉽게 늘릴 수 있어 오버플로우가 발생하지 않는다(용량 제한이 없다). 필요에 따라서는 환형으로 만들 수도 있으며, 환형으로 만들지 않아도 삽입과 삭제가 제한되지 않아 편리하다.

 

데크

• Deque

  • 스택과 큐가 합쳐진 형태로, 양쪽 끝에서 추가/삭제가 이루어진다.

  • L-bottom : 왼쪽 끝의 삽입/삭제가 일어날 위치

  • R-bottom : 오른쪽 끝의 삽입/삭제가 일어날 위치

  • 스크롤(Scroll) : 입력 제한 데크로 삽입을 한쪽 끝에서만 가능하게 한 데크

    • 삭제 - ======데크====== -삽입, 삭제

  • 쉘프(Shelf) : 출력 제한 데크로 삭제를 한쪽 끝에서만 가능하게 한 데크

    • 삽입 - ======데크====== - 삽입, 삭제

• 특징

  • list와 같이 크기가 가변적이다.
  • 앞 뒤에서 데이터 삽입과 삭제가 모두 가능해서 편리하다.
  • 데이터를 중간에 삽입하거나 삭제하는 것이 불편하다.