제6장. 자료구조 arrary list 과 linked list

이전 강의(5장. 프로그래밍 언어)에서 배운 것

프로그래밍 언어의 종류

변수란

자료형(datatype)이란

연산자의 종류

if for 등의 제어구조

함수

 

저번 시간에는 리스트, 튜플, 딕셔너리등 파이썬만이 가지고 있는 독특한 자료구조에 대해 배웠지만 이번 시간에는 일반적인 자료구조와 알고리즘을 간단히 소개할 것이다.

---

 

내용

01. 자료구조의 개요

02. 배열과 연결 리스트

03. 스택과 큐

04. 그래프

05. 트리

 

 

학습목표

• 자료구조의 의미를 이해하고 종류를 알아본다.

• 배열과 연결 리스트의 구조를 이해하고 데이터의 삽입과 삭제 과정을 알아본다.

• 스택과 큐의 구조를 이해하고 데이터의 삽입과 삭제 과정을 알아본다.

• 그래프의 구조를 이해하고 깊이 우선 방법과 너비 우선 방법으로 탐색한다.

• 트리의 구조를 이해하고 이진 탐색 트리에서 데이터의 삽입과 삭제 과정을 알아본다.

 

---

0. 자료구조의 개념

 

1) 컴퓨터는 데이터를 처리하는 기계이다.

2) 대부분의 프로그램은 데이터data를 처리하여 유용한 정보information를 출력한다.

data -> program -> infromation

농구 : 1, 축구 : 2 -> 프로그램 -> 축구가 인기가 더 많다

 

3) 유용한 정보information은 의사결정을 할 수 있게 도와주는 정보입니다.

 

4) 데이터를 어떤 구조를 표현하느냐에 따라 알고리즘의 성능이 달라진다.

5) 자료구조란 프로그램에서 쉽게 이용할 수 있도록 구성된 데이터 간의 논리적인 관계이다.

 

1. 배열

 

1) 배열은 같은 자료형의 데이터를 순서대로 나열한 구조이다.

2) 자료구조의 기본으로 연결리스트와 자주 비교된다.

 

	array list	linked list
연속/ 비연속	연속적인 공간에 순서대로 저장한다.	비연속적인 공간에 순서대로 저장한다.
장점	•indexing이 가능하다. 특정 위치의 요소를 찾기 쉽다. •정렬되어 있다.	•추가 삭제가 쉽다.
단점	•배열의 크기가 정해져 있어 저장할 수 있는 양에 한계가 있다. •추가 삭제가 어렵다.	•메모리 사용량이 조금 더 많다.(pointer) •indexing이 안되어 있다.  특정 위치의 요소를 찾기 위해 앞에서부터 탐색해야한다.

3) 선형 리스트(linear list)란 어떤 순서에 의해 나열된 데이터가 여러 개인 구조이다.

배열, 리스트로 구현할 수 있다.

 

4) 배열은 인덱싱이 가능하다.

인덱스는 첫 번째로부터 떨어진 상대적인 위치, 즉 몇 번째에 있는가를 나타낸다.

배열에서 인덱스의 시작 숫자는 0 또는 1이 올 수 있는데, 대체로 0이 사용된다.

 

1.2 1차원 배열과 2차원 배열의 크기와 주소 구하기

a와 b는 행과 열 인덱스의 시작 번호 n과 m은 행과 열 인덱스의 마지막 번호

 

 

­1차원 배열의 크기를 구하는 공식 : n-a+1

 

­1차원 배열에서 임의의 요소 i가 저장된 주소 : arr[i]의 주소 = base+(i-a)×size

 

 

­2차원 배열의 크기를 구하는 공식 : (n-a+1)×(m-b+1)

배열의 크기가 p행 q열인 경우 ­2차원 배열 arr에서 a[i][j]의 주소를 구하는 공식 :

행 중심 저장 방식→arr[i][j]의 주소=base+(q×(i-a)+(j-a))×size

열 중심 저장 방식→arr[i][j]의 주소=base+(p×(j-a)+(i-a))×size

 

---

 위에서처럼 배열의 크기와 주소 구할 수 있기 때문에 요소에 접근하는 것이 쉽다.

그래서 배열은 항목 접근 속도가 빠르고 일정하다는 장점을 가지고 있다.

 

단점은 사용 전에 크기를 지정해야 한다는 점(메모리를 낭비할 가능성)과 삽입과 삭제가 어렵다는 점이다.

 

 

2. 연결 리스트 linked list

1) 링크드 리스트는 각 데이터들을 포인터로 연결하여 관리하는 구조를 말한다. 
           

2) 각 노드들은 주기억장치의 어느 위치에 저장되든 상관없고, 각 노드들은 포인터로 연결되어 있다.

 

3) 노드가 하나씩 생길 때마다 동적으로 메모리를 할당 받음(malloc()): 필요한 만큼의 메모리만 사용한다.

 

4) 삽입과 삭제가 매우 쉬운 장점을 가지고 있다.

 

2.1 단순 연결 리스트singly linked list

삽입)

 

N ->next = B 대신에 N ->next = A -> next을 써도 된다.

삭제)

2.1 원형 연결 리스트(circular linked list)

단순 연결 리스트는 임의의 노드에서 이전의 노드로의 접근이 불가능하다. 그래서 만들어진 것이 원형 연결 리스트이다. 

1) 원형 연결 리스트는 ­마지막 노드의 포인터 영역이 첫 번째 노드를 가리키는 연결 리스트이다.

 

2) 원형 연결 리스트는 시간이 오래 걸리고 효율적이지 않다.

 

2.2 이중 연결 리스트 (doubly linked list)

1) 이중 연결 리스트는 각 노드에 다음 노드를 가리키는 포인터 영역과 이전 노드를 가리키는 포인터 영역을 포함하는 리스트다. 포인터가 2개다.

 

2) 보통 원형 연결 리스트보다 이중 연결리스트를 사용한다.

 

3) 원형 연결 리스트는 이전, 이후 노드에 쉽게 접근할 수 있다.

 

삽입)

삭제)

2.3 이중 원형 연결 리스트

이중 원형 연결 리스트는 ­이중 연결 리스트의 첫 번째 노드의 이전 노드 포인터 영역이 마지막 노드를 가리키게 하고, 마지막 노드의 다음 노드 포인터 영역이 첫 번째 노드를 가리키도록 구성한 것이다.