자료구조 개론

💡 학습 목표 자료구조란 무엇인가? (Data Structure) 자료구조의 유형

1. 자료구조란 무엇인가? (Data Structure)

자바에서 자료구조는 데이터를 효율적으로 구성하고 조작하기 위한 방법을 제공하는 클래스와 인터페이스의 모음입니다. 이러한 자료구조는 다양한 요구 사항에 맞게 설계되어 있으며, 데이터를 삽입, 삭제, 검색, 정렬 등의 작업을 효율적으로 수행할 수 있도록 지원합니다.

 

자바에서 제공하는 자료구조에는 배열, 리스트, 스택, 큐, 집합, 맵 등이 포함됩니다. 이러한 자료구조는 다양한 상황에서 사용될 수 있으며, 프로그램의 성능과 효율성을 향상시키는 데 중요한 역할을 합니다. 또한 자바 컬렉션 프레임워크(Collection Framework)는 다양한 자료구조를 표준화하여 제공하여, 개발자들이 더욱 쉽게 자료구조를 활용할 수 있도록 도와줍니다.

 

정리

• 프로그램에서 사용할 많은 데이터를 메모리 상에서 관리하는 여러 구현방법들 이다.
• 자료의 효율적인 관리는 프로그램의 수행속도와 밀접한 관련이 있다.
• 여러 자료 구조 중에서 구현하려는 프로그램에 맞는 최적의 자료구조를 활용해야 하므로 자료구조에 대한 이해가 중요함

2. 자료구조의 유형

한 줄로 자료를 관리하기 (선형 자료구조)

 

배열 (Array) : 선형으로 자료를 관리, 정해진 크기의 메모리를 먼저 할당받아 사용하고, 자료의 물리적 위치와 논리적 위치가 같음

 

 

정리

• 배열은 연속된 메모리 공간에 데이터를 저장하므로 특정 인덱스에 직접 접근하여 데이터를 읽거나 쓸 때 매우 효율적
• 배열의 크기를 변경하려면 데이터를 추가하거나 삭제할 때마다 메모리의 다른 위치로 데이터를 이동시켜야 합니다. 이로 인해 추가, 삭제 작업이 많은 경우에는 배열을 사용하는 것이 비효율적
• 특정 위치에 새로운 데이터를 삽입하거나 삭제할 때도 데이터를 이동시켜야 하므로 작업이 번거로움

배열은 검색이 자주 일어나고 데이터가 변경되지 않는 경우에 적합합니다. 추가, 삭제, 수정이 빈번하게 발생하는 경우에는 다른 자료 구조를 사용하는 것이 더 효율적입니다.

 

 

---

 

연결 리스트 (LinkedList) : 선형으로 자료를 관리, 자료가 추가될 때마다 메모리를 할당 받고, 자료는 링크로 연결됨. 자료의 물리적 위치와 논리적 위치가 다를 수 있음

 

리스트에 자료 추가하기 ( 단순 연결 리스트 )

정리

Linked list는 데이터가 추가되고 삭제하는 속도가 배열보다 빠르다.

 

---

스택 (Stack) : 가장 나중에 입력 된 자료가 가장 먼저 출력되는 자료 구조 (Last In First Out)

 

 

---

큐 (Queue) : 가장 먼저 입력 된 자료가 가장 먼저 출력되는 자료 구조 (First In First Out

 

 

---

 

비선형 자료구조 

 

부모 자식의 관계처럼 계층적 관계를 표현하는 데 사용됩니다. 트리는 노드(Node)로 구성되며, 하나의 노드가 다른 노드들과 연결된 구조를 가집니다. 트리 구조에서는 한 노드가 최상위에 위치하며, 이를 루트(Root) 노드라고 합니다. 루트 노드 아래에는 여러 개의 서브트리(Subtree)가 존재할 수 있으며, 각 서브트리도 트리 구조를 이룹니다. 연결된 선은 엣지(Edge)라고 불립니다. 따라서 어떤 두 노드도 정확히 하나의 엣지로만 연결됩니다.

 

트리 (Tree) : 부모 노드와 자식 노드간의 연결로 이루어진 자료 구조 (반대로 뒤집으면 나무 형태와 비슷)

 

이진 트리(Binary Tree): 각 노드가 최대 두 개의 자식을 가질 수 있는 트리입니다. 즉 0부터 2개까지의 자식 노드를 가질 수 있습니다. 요소가 중복되도 상관이 없다.

 

이진 탐색 트리(Binary Search Tree, BST): 이진 트리의 한 종류로, 각 노드에서 왼쪽 서브트리에는 노드의 값보다 작은 값들을, 오른쪽 서브트리에는 노드의 값보다 큰 값들을 가지는 구조입니다.

 

Binary Search Tree 는 목적은 검색을 위해 만들어진 이진 트리이다. 그래서 안에 들어가는 요소가 중본이 되면 안된다.

 

정수 값 23, 10, 48, 15, 7, 22, 56 순으로 자료를 넣을때 (순서대로 자료를 넣었을 때)

이진 탐색 트리는 검색 속도가 빠른 편이다. 단 항상 트리가 안정적으로 구현되는 것은 아니다.

 

편향된 이진 트리를 재정렬하여 균형을 맞추는 트리를 균형 이진 탐색 트리(Balanced Binary Search Tree)라고 합니다.

 

참고

이진 탐색 트리(Binary Search Tree, BST)를 탐색할 때 in-order Traversal (중위 순회) 방식을 사용하면 출력되는 결과 값이 정렬되어서 나올 수 있다.

• 전위 순회(Pre-order), 중위 순회(In-order), 후위 순회(Post-order), 레벨 순회(Level-order)
• 단, 이진 탐색 트리가 아닌 일반적인 이진 트리에서는 탐색 방법에 따라 탐색 결과가 정렬되어 나온다고 보장할 수는 없습니다.

오름차순 정렬

순서: 왼쪽 서브트리 → 현재 노드 → 오른쪽 서브트리 (오름 차순으로 정렬 됨) 방법: 먼저, 왼쪽 서브트리를 재귀적으로 중위 순회합니다. 그 다음, 현재 노드를 방문(데이터 처리)하고, 마지막으로 오른쪽 서브트리를 재귀적으로 중위 순회합니다.

 

위 그림 참고 → 7 , 10, 15, 22, 23, 46, 56 (작은 값에서 큰 값으로 정렬 됨)

💡 재귀적 → 프로그래밍에서 함수나 알고리즘이 자기 자신을 호출하는 과정을 의미합니다 즉, 자기 자신을 다시 호출한다

 

내림차순 정렬: 중위 순회의 변형

순서: 오른쪽 서브트리 → 현재 노드 → 왼쪽 서브트리

 

위 그림 참고 → 56, 48, 23, 22, 15, 10, 7 (큰 값에서 작은 값으로 정렬 됨)