데이터 구조화의 가장 기본적인 방법은 데이터를 나열하는 것이다. 이에 '리스트'는 죽 나열한 데이터를 의미한다.
선형리스트(Linear list 혹은 순서 리스트 Order list)
나열한 자료들 간에 앞뒤 관계가 1대1인 리스트를 의미한다.
리스트는 앞서 표현하며, 원소를 나열한 순서는 원소들 자체의 순서가 된다. 덧붙여서, 공백 리스트, 즉 원소가 하나도 없는 리스트도 엄연히 리스트이다.
-
더보기리스트 연산
리스트를 관라하기 위해서는 연산이 필요하다. 다음은 연산 작업의 예이고, 이러한 연산 목록은 필요에 따라 더하거나 뺄 수 있다.
- 리스트의 두 가지 구현 방식
순차(sequential) 자료구조 방식과 연결(linked) 자료구조 방식이 있다. 장단점이 분명하기에 상황에 맡게 쓴다.
연결 자료구조 방식은 다음에 배울 예정이므로 오늘늘은 순차 연결 방식이 집중적으로 한다.
- 순차 자료구조에 대해
순차 자료구조는 원소들의 논리적 순서와 물리적 순서가 동일하게 메모리에 저장된다. 빈칸은 없어야 한다.
원소들의 논리적 순서 = 원소들이 저장된 물리적 순서
순차 자료구조는 원소 위치를 간단한 주소 계산으로 알아낼 수 있다.
원소 삽입 - 리스트 중간에 원소를 삽입하면, 그 뒤에 원소들은 한자리씩 뒤로 이용해서 물리적 순서를 논리적 순서와 일치시킨다. 원소 삽입시에는 삽입하는 원소의 위치 뒤에 있는 원소가 아니라 맨 뒤에 있는 원소부터 이동시킨다.
원소 삭제 - 리스트 중간에서 원소를 삭제하면, 그 뒤에 원소들을 한 자리씩 앞으로 이동시킨다.
- 2차원 배열의 물리적 저장 방법(위치 알아내는 식)
c나 java는 미묘한 차이가 있을진 몰라도 보통 행 우선 순서방법을 쓴다. 열 우선이나 행 우선이나 배열크기가 작으면 성능차이는 미미하지만 배열크기가 크면 클수록 행우선이 조금 더 유리하다.
다항식의 순차 자료 구조 구현
- 1차원 배열을 이용한 다항식 표현
배열 인덱스 i 위치에 지수 i인 항의 계수를 저장한다.
만약, 다항식이 희소 다항식(대부분의 항의 계수가 0인 다항식을 말함)일 경우 메모리의 낭비가 발생한다.
- 2차원 배열을 이용한 다항식 표현
그럼 연산 구현은 1차 배열보다 왜 복잡한가? 1차 배열은 계수가 없는 항도 배열로 구현되어 있기에 같은 차수의 두 항을 계산해 결과배열에 넣으면 되지만 2차원배열은 차수를 일일히 비교하고 계산하여 넣어야 한다.
행렬의 순차 자료 구조 구현
행렬이란, 행과 열의 조합. 원소(m*n=mn)으로 표현할 수 있음. 행과 열의 갯수가 같은 것을 정방행렬이라 함.
전치행렬: 행렬의 가장 간단한 연산. 행과 열을 서로 교환하여 구성함.
- 행렬 2차 배열 구현과 희소 행렬
다항식의 순차 자료구조에서의 희소 다항식처럼 행렬에도 일부의 유의미한 값만 가지고 있는 희소행렬이 있다. 그럴 때 0이 아닌 원소만 <행번호, 열번호, 원소>쌍으로 배열에 저장하면 된다. 다만, 전체 행의 개수, 전체 열 개수, 0이 아닌 원소의 개수를 0번행에 저장해야 한다.
