[자료구조] 1일차 자료구조란?

자료구조 - 자료를 저장하는 구조

형태에 따라 장단점이 존재하며

구현하려는 프로그램의 성능을 고려하여 알맞은 자료구조를 선택해야한다.

프로그램의 자료를 효율적으로 담기위해 배움.

 

추상적 자료형

• 어떤 자료와 그 자료에 대한 연산(동작)들의 수학적인 정의를 의미한다.
• 그리고 그 정의를 구현하는 방법은 명시되어 있지 않다.

 

자료형

• 어떤 자료가 식별될 수 있는 방법과 그 자료에 대한 여러 가지 연산(동작)을 제공

💡 예시)

65 라는 자료가 수를 나타내는지 알파벨 ‘A’를 나타내는지 자료형을 모르는 경우에는 해석할 수 없다.
자료에 적용할 수 있는 연산을 결정한다. 자료를 특정 분류에 따라 올바르게 표현하기 위한 정의와, 그 구현이 바로 자료형

 

**** 정리) 추상적 자료형, 자료구조 차이 ****

추상적 자료형

• 자료들과, 그 자료들에 대한 연산들을 개념적으로 정의만 한 것

자료구조

• 자료를 저장하는 방법과 자료에 적용할 수 있는 연산을 구체적으로 제공한 것.

추상적 자료형을 구체적으로 구현한 결과가 자료구조

 

배열과 연결리스트

리스트

• 추상적 자료형
• 순서가 존재하며, 일렬로 나열된 값들이 들어있다.

리스트가 담는 자료에 적용되는 연산

1. 조회 : 임의의 위치의 자료가 무엇인지 알아본다.
2. 삽입 : 임의의 위치에 자료를 추가한다.
3. 삭제 : 임의의 위치의 자료를 제거한다.
4. 외 여러가지가 있다

배열

• 리스트라는 추상적 자료형을 구현한 대표적인 예

조회

: 특정 순서값 조회

ex) 5번 인덱스 찾으신 분!! → 2 !!

 

삽입

: 새로운 자료가 추가되면서, 자료들의 순서를 변경해줘야해서 조금 번거롭다.

ex) 3번 인덱스에 10을 추가합시다!!

→ 공간을 하나 늘려서 인덱스가 8번까지 생기고 3부터 뒤로 미뤄서 넣기

 

삭제

: 제거할 인덱스의 자료를 비운다.

ex) 5번 인덱스의 자료를 제거합시다!!

→ 남는 공간은 제거!

 

연결 리스트(Linked List)

• 리스트를 구현한 자료구조 중 대표적인 다른 예시
• 여러 개의 ‘노드’를 저장하는 방식으로 구현한다.

💡 자료 : 저장하는 값 자체를 의미 포인터 : 자신의 다음 순서의 노드를 가리킴.

→ 그래서 특정 위치의 자료를 찾는 것이 번거로움.
하지만! 자료의 추가와 삭제에서 장점이 있음!!
인덱스를 이용하여 절대적인 순서를 표현하는 배열과는 달리, 연결 리스트는 자신의 다음 노드를 가리키는 상대적인 순서를 표현한다.

 

 

1. 삽입
ex) 3번째 위치에 10을 추가하자!!

 

• 2번째 노드와 3번째 노드의 연결 끊기
• 3번째 위치에 새로운 노드로 연결

 

 

2. 삭제

ex) 4번째 위치의 자료를 제거하자!!

 

- 4번째 위치 찾기

- 제거할 노드 이전과 다음을 다이렉트로 연결

 

 

배열과 연결리스트 차이

배열 연결 리스트

장점	특정 위치의 자료 탐색	자료의 삽입과 삭제
단점	자료의 삽입과 삭	특정 위치의 자료 탐색

 

 

 

자료구조의 구현 방법

**** 객체지향 프로그래밍에서 ****

추상적 자료형 = 인터페이스

자료구조 = 클래스 로 생각할 수 있음.

인터페이스란?

• 객체지향 구조에서 추상 메서드만으로 이루어진 설계용 클래스
  • 추상 메서드: 구현 부분이 비어있는 메서드, 상속 받는 클래스에서 구현하여 사용
• ‘리스트’라는 인터페이스에는 “삽입과 삭제를 지원해야 한다”라는 명세만 주어지고 실제 동작 부분은 리스트를 상속받은 배열 클래스, 연결 리스트 클래스에서 구현해야한다.

자료구조의 구현

• 자료구조를 만드는 데에는 클래스가 탁월 ’필드’ 가 자료에 해당/ ‘메서드’ 가 자료에 적용할 수 있는 연산

예시)

//파이썬
import queue
q = queue.Queue();

→ 큐 자료구조의 자료 저장 및 연산 방법을 갖추고 있다.