자료구조 개념 정리 - 개념 및 종류 이해

자료구조
자료구조란 간단히 말하면 데이터를 효율적으로 처리하게 컴퓨터에 저장하는 방법입니다.
꼭 알아야 하는 개념이며, 잘 설계된 자료구조는 처리되는 실행시간과 최소한의 메모리로 연산을 수행합니다.

기본적으로 프로그래밍을 하며 자료구조를 계속 써왔습니다.
다만, 자료구조를 먼저 공부하지 않았다면 이게 자료구조였다는걸 인지하지 못할 뿐이죠.

자료구조의 종류로는 자료형의 따라 분류하는 단순 구조와 자료 간 관계가 1 대 1인 선형 구조, 1 대 다 혹은 다 대 다 구조인 비선형 구조, 마지막으로 파일 구조가 있습니다.

자료구조의 관점

• 자료형
  자료형은 자료(변수)가 갖는 값의 종류를 표현 한 것이고, 이때 연산은 그 자료형에 맞게 별도/부가적/부차적으로 수행되는 관점입니다.
• // C,C++,java등등 자료(변수) 표현 int a = 1; char b = '1';
• 추상자료형
  각각의 연산에 대한 연산 복잡도가 정의된 가상의 자료 저장 공간입니다.
• 기능의 구현 부분을 나타내지 않고 순수하게 기능이 무엇인지 나열한 것을 추상 자료형*이라고 합니다.위와같이 밥솥의 내부적으로는 기능을 실행하기 위해 어떤 것들이 발생되는지는 전혀 나타내지 않는다는 것이죠.
  추상자료형은 이처럼 구현자와 사용자를 분리해 줍니다.
  예를 들어, 러이브러리를 가져다가 쓰거나 내장 함수를 사용하는 것도 추상 자료형의 정의라고 볼 수 있고, 추상자료형에 대한 구현은 외부로 부터 숨겨져 정보 은닉이 됩니다. 대표적으로 추상팩토리, 추상클래스등에서 공통의 알고리즘을 정의하고 하위 클래스에서 동작하는 구현 방식도 추상 자료형이라 보면 될 것 같습니다.
• 추상적 자료형은 인터페이스와 구현을 분리하여 추상화 계층을 둔 것이다. 예를 들어, 전기 밥솥을 추상적 자료형에 비유한다면, 그 속에 들어가는 밥은 자료가 되고, 밥솥에 있는 취사, 예약취사 버튼들과 남은 시간을 표시하는 디스플레이에 어떤 내용들이 표시되어야 하는지를 명기한 것이다. 추상적 자료형에서는 이것들이 어떻게 구성되는지 관심이 없고, 몇 와트의 전기를 소모하는지에 대해서도 관심이 없다.(위키백과)

자료 구조 리스트
리스트는 두가지 기준에 따라 기초적으로 구분됩니다.
배열리스트(Array List)와 연결리스트(Linked List)

• 배열리스트
  

  

• 연결리스트
  

  

일단 종류별 이론적 설명을 보죠.

배열 - 가장 일반적인 구조이고 메모리상에 같은 타입의 자료가 연속적으로 저장되는 형태.
튜플 - 둘 이상의 자료형을 묶음으로 다루는 구조.
연결리스트 - 노드를 단위로 하여, 자료와 다음 노드를 가르키는 참조값으로 구성, 노드가 다음 노드로 아무것도 가르키지 않으면 리스트가 끝나는 구조.
원형 연결 리스트 - 각 노드는 다음 노드를 가르키고, 마지막 노드가 처음 노드를 가리키는 연결리스트.
이중 연결 리스트 - 각 노드는 이전 노드와 다음 노드를 가리키는 참조값으로 구성, 처음 노드의 이전 노드, 그리고 마지막 노드의 다음 노드는 없다.
환형 이중 연결 리스트 - 처음 노드가 이전 노드로 마지막 노드를 가르키고, 마지막 노드가 다음 노드로 처음 노드를 가르키는 이중 연결 리스트.
해시 테이블 - 개체가 해시값에 따라 인덱싱 됨.

선형구조
선형구조란 자료들을 순차적으로 나열시킨 형태라고 볼 수 있습니다.
이해를 위해 그림을 좀 보겠습니다.

이렇게 1:1 관계로
즉, 1-2-3-4 순서대로 나열된 형태를 의미하고, 데이터가 연속적으로 연결되어 있는 모양으로 구성하는 방법입니다.

선형구조는 대표적으로 배열,연결리스트,스택,큐,덱로 5가지가 있습니다.

배열
배열의 종류는 1,2,3차원 배열이 있고, 각자의 계산 방법이 있는데, 각각의 계산방법을 알아보죠.

비선형구조
비선형구조란 하나의 자료뒤에 여러개의 자료가 존재하는 것을 가르킵니다.

이렇게 1:n 관계로
즉, 1뒤에 2,3, 2뒤에 4,5로 이진트리 형태의 자료를 의미합니다.

비선형구조는 대표적으로 트리,그래프 2가지가 있습니다.