선형 구조 [자료구조 정리②]

배열의 개념

• 선형 구조

선형 자료구조는 데이터가 일렬로 연결되어 있는 자료구조를 말한다. 이러한 자료구조는 데이터를 순차적으로 저장하고 접근하는데 사용된다. 대표적인 선형 자료구조로는 배열 (Array)과 연결 리스트 (LinkedList)가 있다. 배열은 정해진 크기의 메모리를 먼저 할당받아 사용하며, 자료의 물리적 위치와 논리적 위치가 같다.

 

• 배열

배열은 프로그래밍에서 많이 사용되는 선형 자료구조다. 이는 동일한 데이터 타입의 요소들이 순서대로 저장되는 공간이기도 하다. 배열은 다음과 같은 특징을 가지고 있다.

1. 정적 크기: 배열은 미리 정해진 크기를 가지며, 크기를 변경할 수 없다. 예를 들어, 정수형 배열 int[] numbers = new int[5];은 5개의 정수를 저장할 수 있는 공간을 생성한다.
2. 인덱스 기반 접근: 배열의 각 요소는 인덱스를 통해 접근된다. 첫 번째 요소는 0번 인덱스, 두 번째 요소는 1번 인덱스, 그리고 마지막 요소는 (크기 - 1)번 인덱스에 저장된다.
3. 연속된 메모리 공간: 배열은 연속된 메모리 공간에 요소를 저장한다. 이는 빠른 접근 속도를 제공한다.

배열을 선언하고 초기화하는 방법은 다음과 같다.

// 정수형 배열 선언과 초기화
int[] numbers = new int[5]; // 크기가 5인 배열 생성
numbers[0] = 10; // 첫 번째 요소에 10 저장
numbers[1] = 20; // 두 번째 요소에 20 저장
// 나머지 요소도 마찬가지로 초기화

// 문자열 배열 선언과 초기화
String[] names = {"Alice", "Bob", "Charlie"}; // 크기가 3인 배열 생성

 

• 1차원 배열

1차원 배열은 같은 자료형을 가진 여러 개의 자료 (변수)들을 하나의 이름으로 묶은 자료들의 집합이다. 이 집합을 이루는 각각의 자료를 요소라고 하는데, 이 요소는 모두 같은 자료형을 가지고 있으며 배열의 요소 중 몇 번째 요소에 접근할 것인지를 명시해 주는 대괄호 ( [ ]) 사이의 숫자를 첨자라고 한다.

 

1차원 배열은 데이터를 1열로 나열할 수 있기 때문에 이렇게 불린다. 예를 들어, 정수형 배열 int a[5]은 5개의 정수를 저장할 수 있는 공간을 생성한다. 배열의 첨자는 0부터 시작하며, a[0], a[1], …, a[4]와 같이 요소를 참조한다. 배열은 대량의 데이터를 반복문으로 처리하거나 여러 개의 기억장소를 효율적으로 확보할 때 유용하게 사용된다.

 

• 다차원 배열

다차원 배열은 2차원 이상의 배열 체계를 의미한다. 주로 2차원 배열과 3차원 배열을 말하는데요, 이들은 다음과 같은 형태를 가진다.

1. 2차원 배열: 1차원 배열이 여러 개가 뭉쳐있는 구조로, 평면 구조를 띈다. 예를 들어, 아파트의 층별로 가구가 배열되는 것처럼 생각할 수 있다.
2. 3차원 배열: 2차원 배열의 위로 여러 개가 쌓인 형태로, 직육면체 구조를 가진다.

2차원 배열은 행렬과 유사한 구조를 가지며, 세로와 가로의 길이를 명시하여 선언한다. 예를 들어, int arr[3][4]는 세로가 3, 가로가 4인 2차원 배열을 생성합니다. 3차원 배열은 2차원 배열을 여러 겹으로 쌓아 만든 구조이며, 세로, 가로, 높이의 길이를 명시하여 선언한다.

 

스택의 개념

스택은 컴퓨터에서 많이 사용되는 자료구조로, 후입선출 (LIFO: Last-In First-Out) 방식을 따른다. 이것은 가장 최근에 추가된 데이터가 가장 먼저 제거되는 것을 의미한다.

 

예를 들어, 스마트폰의 “뒤로 가기” 키를 눌렀을 때 현재 수행 중인 앱이 종료되고 직전에 수행되던 앱이 다시 나타나는 상황에서 스택이 사용된다. 이때 스택은 '쌓아놓은 더미’를 의미하며, 식당에 쌓여있는 접시 더미나 책상 위의 책과 같은 예시도 스택의 개념을 잘 설명해준다. 프링글스도 스택의 대표적인 예시 중 하나다.

 

• 스택의 연산

1. 삽입 (Push):
   1. 스택의 가장 마지막 위치에 데이터를 추가한다.
   2. 예를 들어, 스택의 이름이 my_stack이라면 my_stack.push(넣을_데이터)를 호출하면 된다.

1. 삭제 (Pop):
   1. 스택의 가장 마지막 위치에서 데이터를 제거한다.
   2. 예를 들어, my_stack.pop()을 호출하면 가장 최근에 추가된 데이터가 삭제된다.

큐의 개념

큐는 데이터를 일시적으로 저장하거나 처리하는 자료구조다. 먼저 들어온 데이터가 먼저 처리되는 특성을 가지며, 이를 FIFO (First In First Out) 구조라고 한다. 큐는 다양한 상황에서 활용된다. 예를 들면 프린터의 출력 처리, 윈도 시스템의 메시지 처리기, 프로세스 관리 등 데이터가 입력된 순서대로 처리해야 할 필요가 있는 상황에서 사용된다. 큐는 다음과 같은 연산을 지원한다.

1. Enqueue (put): 큐에 자료를 넣는 연산입니다.
2. Dequeue (get): 큐에서 자료를 꺼내는 연산입니다.

큐는 선형 큐와 환형 큐로 나뉜다. 선형 큐는 막대 모양으로 된 큐로 크기가 제한되어 있고 빈 공간을 사용하려면 모든 자료를 꺼내거나 자료를 한 칸씩 옮겨야 하는 단점이 있다. 반면, 환형 큐는 선형 큐의 문제점을 보완한 구조로, 원형으로 연결하여 데이터를 처리한다. 연결 리스트를 사용한 큐도 있으며, 큐의 길이를 쉽게 늘릴 수 있어 오버플로우가 발생하지 않는 특징이 있다.

 

리스트의 개념

리스트는 자료구조의 일종으로, 순서를 가진 항목들의 모임을 의미한다. 이러한 리스트는 다양한 연산을 통해 관리할 수 있다. 자료구조는 크게 선형 자료구조와 비선형 자료구조로 나뉘는데, 리스트는 선형 자료구조에 속한다.

 

리스트의 주요 특징은 다음과 같다.

1. 항목들의 순서를 가지며, 위치를 지정할 수 있다.
2. 삽입, 삭제, 탐색 등 다양한 연산이 가능하다

.

리스트는 정적 구현과 동적 구현으로 나눌 수 있다.

1. 정적 구현 (Static Implementation):
   • 배열 (Array)을 사용하여 리스트를 구현한다.
   • 배열은 간단하게 구현할 수 있고 속도가 빠르지만 크기가 고정되는 단점이 있다.
2. 동적 구현 (Dynamic Implementation):
   • 연결 리스트 (Linked List)를 사용하여 리스트를 구현한다.
   • 연결 리스트는 삽입과 삭제가 효율적이며 크기가 제한되지 않는 장점이 있다.

단순 연결 리스트

단순 연결 리스트는 동적 메모리 할당을 이용하여 노드들을 한 방향으로 연결하여 리스트를 구현한 자료구조다. 이 리스트는 삽입이나 삭제 시 항목들의 이동이 필요 없어 효율적이다.

 

주요 특징은 다음과 같다:

• 물리적으로 연결되지 않은 데이터가 연결된다.
• 각 노드는 자기 후속 노드와 연결되어 있으며, 하나의 링크 필드를 가진다.
• 마지막 노드의 링크 필드는 리스트의 끝을 표시하는 null 값을 가진다.

단순 연결 리스트는 웹 브라우저에서 링크를 관리하거나 데이터베이스에서 파일 시스템을 관리할 때 많이 사용된다. 인덱싱은 불가능하지만 중간에 삽입과 삭제 연산이 배열보다 빠르다는 장점이 있다.

 

이중 연결 리스트

이중 연결 리스트는 각 노드가 두 개의 포인터를 가지며, 이전 노드와 다음 노드를 가리키는 형태의 선형 자료구조이다. 이중 연결 리스트는 기존 단순 연결 리스트의 단방향 흐름을 극복하기 위해 양방향으로 움직일 수 있도록 만들어진 구조다.

 

주요 특징은 다음과 같다:

• 각 노드는 데이터와 두 개의 포인터 (하나는 이전 노드를, 다른 하나는 다음 노드를 가리킴)를 가지고 있다.
• 리스트의 시작점은 "헤드 (Head)"라 불리며, 끝은 "테일 (Tail)"이라고 한다.
• 이중 연결 리스트는 양방향 탐색이 가능하므로 특정 인덱스 위치의 요소를 가져오거나 반복자를 이용한 탐색에 유용하다.

이중 연결 리스트의 장단점은 다음과 같다:

• 장점:
  • 양방향 탐색: 노드가 이전과 다음 노드를 모두 가리키기 때문에 양방향 탐색이 가능하다.
  • 삽입과 삭제가 빠름: 특정 위치에서 삽입과 삭제가 빠르다.
• 단점:
  • 더 많은 메모리 사용: 각 노드가 두 개의 포인터를 저장하기 때문에 추가적인 메모리 사용이 필요하다.
  • 구현이 복잡: 단일 연결 리스트보다 구현이 더 복잡하다.

 

자료구조 1 ~ 76p. 정리 완료

2024. 6. 18. 단국소프트웨어고등학교 조성진

E-MAIL1: pianist@abracadabra.im

E-MAIL2: dk23036@dankook.sen.hs.kr