단순 구조는 프로그래밍 언어에서 제공하는 기본 데이터 타입을 말한다.
선형 구조는 자료들 사이의 앞뒤 관계가 일대일(1:1) 로 구성된다.
비선형 구조는 자료들 사이의 앞뒤 관계가 계층 구조 혹은 망 구조로 이루어진다.
파일 구조는 보조기억장치(HDD 등)에 저장되는 파일에 대한 자료구조를 말한다.
추상 자료형(Abstract Data Type, ADT): 자료구조를 표현하는 가장 대표적인 방법 중 하나
자료구조를 사용할 수 있는 인터페이스를 정의한다. (혹은 자료구조의 연산들을 정의)
어떻게(How) 구현이 이루어지는 지를 정의하지 않고, 무엇(What)인지를 정의한다.
정보 은닉의 특징을 가진다.
정보 은닉: 중요한 정보만 나타내고, 중요하지 않은 정보는 숨기는 것
원칙적으로는 배열은 변수를 초기화한 후에 사용해야 한다.
두 가지 방식의 초기화 방법
문자열 배열의 경우
{0, }
으로 초기화하지 않을 경우, 문자열 마지막에 널 문자(\0
) 추가하는 것을 깜빡할 수 있다. 즉, str[5] = '\0'
를 잊어버리면 릴리즈시 문제가 발생한다.배열의 원소가 배열 자료형인 배열
예) 2차원 배열의 각 원소는 1차원 배열이다.
다차원 배열 배열의 초기화 방식
자료를 순서대로 저장하는 자료구조를 말한다.
일직선으로 연결된(Sequential) 자료
- 예를 들어, 아래 그림의 중간에서처럼 파일 목록 중 하나가 삭제되었다고 생각해보자. 배열과 달리 리스트의 경우, 중간이 비어있으면 안 된다. (리스트는 요소끼리 서로 연결되어 있어야 한다.) 따라서 제거된 파일 다음의 요소들을 한 칸씩 위로 올려야 한다.
- 또 하나, 마지막 부분에서처럼 새로운 파일이 목록 중간에 하나 추가되었다고 해보자. 배열은 해당 인덱스의 값을 덮어쓰지만, 리스트는 해당 인덱스부터 한 칸씩 뒤로 밀려나고 새로운 파일이 중간에 추가된다.
배열을 이용하여 구현된 리스트
논리적 (저장) 순서와 물리적 (저장) 순서가 동일하다.
원소의 위치 인덱스는 0부터 시작한다. (배열과 동일)
배열과 다르게 모든 자료가 일직선으로 연결되어 있어야 한다. (중간에 자료가 끊기면 안 된다.)
배열 리스트의 원소 추가
배열과 달리 배열 리스트는 원소를 중간에 추가할 수 있다.
원소를 추가하기 전 기존 원소들을 한 칸씩 이동하는 연산이 필요하다.
배열 리스트의 원소 제거
Q. 원소의 개수가 10만 개인 배열 리스트에서 원소의 추가/제거가 빈번하게 발생한다면?
A. 인덱스 0의 원소를 삭제한다면, (10만 - 1)개 만큼의 원소를 이동해야 한다. 이에 따르면 삭제하려는 원소와 관계없는 원소들까지 이동시켜줘야 하는 불편함이 생긴다.
연결 리스트라고도 불리며, 연결 포인터를 이용하여 구현한다.
배열 리스트와 달리 논리적 (저장) 위치만 순차적이고, 물리적 (저장) 위치는 순차적이지 않을 수 있다. (최대 원소 개수 지정에서 차이가 발생한다.)
연결 리스트를 구성하는 기본 단위는 노드이다.
노드: 자료(Data) + 링크(Link)
연결 리스트에서 노드의 추가와 제거는 링크의 추가와 제거를 의미한다. (배열 리스트에서는 원소의 이동이 곧 추가와 제거를 의미)
연결 리스트의 노드 추가
예) 인덱스 1에 새로운 원소 5를 추가
연결 리스트의 노드 제거
예) 인덱스 2의 원소 제거
연결 리스트의 장점 (배열 리스트의 단점)
연결 리스트의 단점 (배열 리스트의 장점)