선형 리스트(Lenear List) 개요

선형구조

- 스택

 * 스택 자료구조에 먼저 저장된 것이 꺼내어 쓸 때는 제일 나중에 나옴

 * 반대로 가장 최근에 저장된 것이 꺼내어 쓸 때는 제일 먼저 나옴

 * 만약 자료들의 나열 순서를 바꾸고 싶다면 스택에 집어 넣었다가 꺼내면 역순으로 바뀜

 

- 큐

 * 스택과 반대로 큐 자료 구조에 먼저 저장된 것이 제일 먼저 나옴

 * 가장 나중에 저장된 것이 꺼내어 쓸 때는 가장 나중에 나옴

 

- 환형 큐

 * 한정된 길이 안에서 부수적인 작업 없이 읽고 쓰기를 할 수 있는 큐임

 * 원형으로 구성된 큐

 

- 덱

 * 양쪽에서 넣기와 빼기를 할 수 있는 일반화된 선형 구조임

 

비선형구조

- 그래프

 * 꼭지점과 꼬지점을 잇는 변으로 구성됨

 

- 유향/무향 그래프

 * 변이 방향성을 갖는지 갖지 않는지에 따른 그래프의 분류임

 

- 트리

 * 뿌리와 뿌리 또는 다른 꼭지점을 단 하나의 부모를 갖는 꼭지점들로 이루어진 구조

 * 부모 자식 관계는 변으로 표현됨

 cf_1) 무향 그래프의 경우 순환이 없는 연결 그래프를 뜻함

 cf_2) 무향 그래프의 경우 변의 방향은 보통 부모를 기리키도록 구현됨

 

- 이진 트리

 * 자식이 최대 두 개인 트리

 

- 힙

 * 이진 트리의 일종으로 이진 트리에 어떤 특성을 부여한 것이라 할 수 있음(계층 순서화)

 

리스트와 선형 리스트

1. 리스트(List)

- 리스트의 정의

 * 자료를 나열한 목록

 * 목록이나 도표처럼 여러 데이터를 관리할 수 있는 자료형을 추상화시킨 것

 * 데이터 삽입, 삭제, 검색 등 필요 작업을 가함

 * 스택과 큐는 리스트의 특수한 경우에 해당

 

2. 선형 리스트

- 선형 리스트의 정의

 * 순서 리스트(Ordered List)

 * 자료들 간에 순서를 갖는 리스트

 

선형 리스트의 자료구조

1. 표현 형식

- 리스트의 표현 형식

 * 리스트 이름 = (원소1, 원소2, ..., 원소n)

 * 선형 리스트에서 원소를 나열한 순서는 원소들의 순서가 됨

 

2. 저장

- 선형 리스트의 저장

 * 원소들의 논리적 순서와 같은 순서로 메모리에 저장

 * 순차 자료구조

  - 원소들의 논리적 순서 = 원소들이 저장된 물리적 순서

 

- 순차 자료구조의 원소 위치 계산

 * i번째 원소의 위치 = a + (I-1) x ℓ

  - 선형 리스트가 저장된 시작 위치 : a

  - 원소의 길이 : ℓ (byte의 개수)

 

선형 리스트의 삽입과 삭제

1. 삽입

- 선형 리스트의 원소 삽입

 * 선형 리스트 중간에 원소가 삽입되면, 그 이후의 원소들은 한자리씩 자리를 뒤로 이동하여 물리적 순서를 논리적 순서와 일치시킴

- 원소의 삽입 방법

 1) 원소를 삽입할 빈 자리를 반들기

  - 삽입할 자리 이후의 원소들을 한자리씩 뒤로 자리 이동(연산의 지연 원인)

 2) 준비한 빈 자리에 원소 삽입하기

 

- 삽입할 자리를 만들기 위한 자리 이동 횟수

 * n+1개의 원소로 이루어진 선형 리스트에서 k번 자리에 원소를 삽입하는 경우

  : k번 원소부터 마지막 인덱스 n번 원소까지 (n-k+1)개의 원소를 이동

 

2. 삭제

- 선형 리스트의 원소 삭제

 * 선형 리스트 중간에서 원소가 삭제되면, 그 이후의 원소들은 한자리씩 자리를 앞으로 이동하여 물리적 순서를 논리적 순서와 일치시킴

- 원소 삭제 방법

 1) 원소 삭제하기

  - 삭제한 자리 이후의 원소들을 한자리씩 앞으로 자리 이동(지연 원인)

 

 

- 삭제 후, 빈자리를 채우기 위한 자리 이동 횟수

* n+1개의 원소로 이루어진 선형 리스트에서 k번 자리에 원소를 삭제한 경우

  : (k+1)번 원소부터 마지막 n번 원소까지 (n-(k+1) + 1)개의 원소를 이동

이동 횟수 = n-(k+1)+1) = n-k