[자료구조] <순차 자료구조> 선형 리스트, 행렬의 선형 리스트 표현

 

자료구조

자료를 효율적으로 표현하고 저장하고 처리할 수 있도록 정리하는 것

 

자료구조 분류

1. 단순구조
   • 프로그래밍 언어에서 제공하는 정수, 실수, 문자, 문자열 같은 데이터 타입
2. 선형구조
   • 자료 사이 관계가 1:1
3. 비선형구조
   • 자료 사이 관계가 1:다 / 다:다 
4. 파일구조

 

선형구조

1. 순차 리스트
   • 자료의 논리적 순서와 관계 없이 기억 장소에 저장되는 물리적 순서가 일치하는 구조
2. 연결 리스트
   • 자료의 물리적 순서와 관계 없이 포인터를 사용하여 논리적인 순서로 연결하는 구조
3. 스택
4. 큐
5. 데크

 

 

 

순차 자료구조

구현할 자료들을 논리적인 순서대로 메모리에 연속하여 저장하는 구현방식

논리적 순서와 물리적 순서가 항상 일치해야 한다

 

EX) 배열

 

삽입,삭제 연산을 해도 빈자리 없이 자료가 순서대로 연속하여 저장된다

( 중간이 비면 뒷 자료들을 앞으로 땡김 / 중간에 삽입하면 기준점 뒷 자료들을 뒤로 밀어재낌 )

 

 

 

선형 리스트 (순차 리스트)

원소를 순서대로 나열한 리스트, 순서를 가진다

 

선형 리스트(선형 순차 리스트)는 원소들이 나열된 논리적 순서와 메모리에 저장되는 물리적 순서가 일치하는 순차 자료구조 방식으로 구현

순차 자료구조는 원소들이 순서대로 연속해서 저장되기 때문에 시작위치, 원소 크기를 알면 특정 원소의 위치를 쉽게 알 수 있다

 

선형 리스트에서 원소 삽입

선형 리스트는 순차 자료구조 방식으로 구현하기 때문에

삽입 후 변경된 논리적 순서와 메모리에 연속 저장된 물리적 순서가 일치해야 한다

따라서 먼저 물리적으로 삽입할 자리를 만든 다음 원소를 삽입해야 한다

물리적으로 삽입할 자리를 만드려면 삽입할 위치 뒤에 있는 원소들을 전부 한 자리씩 뒤로 옮겨야 한다

위 그림을 보면

1번에서 물리적으로 삽입할 자리를 만들기 위해 삽입할 위치 뒤에 있는 원소를 전부 한 자리씩 뒤로 옮기고 있다

2번에는 그렇게 만들어진 물리적 자리(메모리)에 원소를 삽입해주었다

 

원소가 n개인 선형 리스트에서 k번 자리에 원소를 삽입할 때 k번부터 마지막 원소인 (n-1)번까지 이동하는 횟수는

(n-1)-k+1 번이다

 

 

 

선형 리스트 구현

ㄴ 1차원 배열

인덱스를 1개만 사용한다

 

ㄴ 2차원 배열

행 인덱스와 열 인덱스를 사용한다

 

ㄴ 3차원 배열 순차 표현

면 인덱스, 행 인덱스, 열 인덱스를 사용한다

 

3차원 배열의 구조는 논리적인 구조일 뿐, 메모리에 저장되는 물리 구조는 2차원 배열처럼 1차원의 선형 구조가 된다

 

순차 자료구조를 사용할 때는?

물리적으로 원소들을 옮기는 연산은 추가적인 오버헤드가 발생한다

따라서 읽기/쓰기/순차 액세스 같은 연산은 효율적이나

삽입/삭제 연산을 많이 사용할 경우에는 비효율적이다

 

 

 

 

행렬의 선형 리스트 표현

행렬이란?

행과 열로 구성된 자료 구조이다

• 정방행렬
  • 행 개수 = 열 개수인 행렬
• 전치행렬
  • 행렬의 행과 열을 바꿔 구성한 행렬
• 희소행렬
  • 행렬 값에 0이 대부분을 차지하는 행렬
  • 실사용하지 않는 공간이 많아서 공간활용도가 낮다

 

희소행렬 새로 구성하기

0이 아닌 값이 있는 원소만 따로 배열로 구성할 수 있다