자료와 자료구조

1. 텍스트 자료의 표현

ASCII : 7비트로 구성되며, 각각의 비트 조합은 128개의 고유한 문자를 나타냅니다.

유니코드 : 유니코드에 먼저 등록된 영어와 숫자같은 문자는 1byte ,

그뒤에 등록된 문자는 4byte와 같이 차별적 혹은 가변적으로 할당하는 방법을 택했습니다.

2. 숫자 자료의 표현

부호 없는 정수, 부호 있는 정수, 실수 (부동 소수점 표현 방식)

3. 선형/비선형 자료 구조

4.  선형 자료구조

4-1. 배열

[ 배열의 특징 ]

1. 순서가 있습니다. (메모리 순서대로)
2. 연속된 공간을 '미리' 정해서 사용해야 합니다. (확정된 메모리 공간을 할당받아 써야 하므로)
3. N번째 데이터에 접근하기 위해 복잡한 과정 필요없이 그냥 덧셈과 곱셈 한번이면 가능합니다. (n번째 데이터 접근 : 시작 주소 + (n-1) * 해당 자료형 크기)

 💡 배열의 시간복잡도

• 데이터 읽기, 수정 : O(1)
• 데이터 추가, 삭제 : O(N)
• 예외 : 배열에 빈 공간이 존재하는걸 허용하며 짜는 경우라면 마지막 데이터의 추가, 삭제는 O(1) </aside>

4-2. 리스트 (LinkedList)

링크드 리스트는 일반적인 리스트로 불리며, 노드로 연결된 데이터를 저장하는 자료구조입니다. 링크드 리스트는 데이터의 순서를 유지할 수 없지만, 데이터를 추가하거나 삭제하는 것이 쉽습니다. 또한, 배열과 달리 배열의 크기를 우리가 지정하거나 변경할 필요가 없습니다.

 

• 배열은 메모리 자체에 순서대로 들어가 있으므로 다음 데이터는 물론이고, n번째 데이터도 쉽게 알 수 있다.
• 하지만 리스트는 현재 그림상으로는 리스트에서 첫번째 데이터인 '12'의 위치는 알 수 있지만 n번째 데이터는 커녕 바로 다음 데이터도 어디에 있는지 알 수 없다.

[ 배열 vs 리스트 ]

• 리스트
  • 일반적으로 데이터의 추가, 삭제가 많은 경우 리스트를 사용하는 것이 효율이 좋습니다.
• 배열
  • 데이터가 자주 추가, 삭제 되지 않고, 읽고 수정하는 경우가 많을 때 배열을 사용하는 것이 효율이 좋습니다.

4-3. 벡터(ArrayList)

기본 동작 원리 및 CRUD에 따른 효율성은 모두 배열과 동일합니다.

 

리스트라고 하면 LinkedList를 뜻합니다.

1. 메모리에서 좀 손해를 보면 (trade-off) 배열이 가득 찼을 경우 미리 1.5배~2배 크기의 새로운 배열을 만드는 식으로 배열도 미리 크기를 설정하지 않고 가변크기'처럼' 사용할 수 있다. 효율성은 당연히 배열과 동일합니다. 그걸 일반적으로 Vector라고 한다. 다만 자바에서는 그걸 추가로 ArrayList라고도 합니다.

 

자바에서의 ArrayList == 리스트? X

자바에서 ArrayList는 배열을 Collection 프레임워크의 List 인터페이스에 맞춰 사용할 수 있도록 만들어둔 것 뿐입니다.

자바에는 실제 Vector 라는 자료구조가 존재합니다.

차이점으로는 Vector는 한 번에 하나의 Thread에서만 쓸 수 있고, ArrayList는 여러 Thread에서 쓸 수 있습니다.

 

4-4. Queue, Stack(큐, 스택+덱)

큐 (Queue)

큐는 FIFO(First in First out; 선입 선출)의 특징을 가지는 자료구조이다. 먼저 들어간 데이터가 먼저 나옵니다.

 

스택 (Stack)

스택은 LIFO(Last in First out; 후입 선출)의 특징을 가지는 자료구조이다. 나중에 들어간 데이터가 먼저 나옵니다.

 

덱 (Deque = Double-ended Queue)

• Double-ended Queue라는 의미로, 양쪽으로 넣고 뺄 수 있는 큐 입니다.
• 당연히 양쪽으로 넣고 뺄 수 있는 스택으로도 쓸 수 있고, 한쪽은 스택 한쪽은 큐로 써도 됩니다.
  • 좀 더 유연한 스택, 큐 입니다.
  • 하지만 리스트와 다르게 중간의 데이터를 건드릴 수 없고, 양끝단만 건드릴 수 있습니다.

5. 비선형 자료 구조

 

5-1. Hash Table(맵)

• key: value로 저장하는 데이터 구조
• 키를 통해 바로 데이터를 받아올 수 있어 속도가 획기적으로 빨라짐
• 해쉬 : 임의 값을 고정 길이로 변환하는것
• 해쉬 테이블 : 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조
• 해쉬 함수 : 키에 대해 산술 연산을 이용해 데이터 위치를 찾을 수 있는 함수
• 해쉬 값 / 해쉬 주소 : 키를 해싱 함수로 연산해서 해쉬 값을 알아내고 이를 기반으로 해뷔 테이블에서 해당 키에 대한 데이터 위치를 일관성있게 찾을 수 잇음
• 슬롯 : 한 개의 데이터를 저장할 수 있는 공간
• 저장할 데이터에 대해 키를 추출할 수 있는 별도 함수도 존재할 수 있음

5-2. Set(셋)

• 데이터를 비순차적(unordered)으로 저장할 수 있는 순열 자료구조 (collection).
• 집합의 개념과 같다고 생각하면 된다.(집합 역시 {1, 9, 6, 4}처럼 중복과 순서가 없다.)
• 삽입(insertion) 순서대로 저장되지 않는다. 즉 특정한 순서를 기대할 수 없는 자료구조.
• 수정 가능합니다.(mutable)
• 동일한 값을 여러번 삽입 불가능합니다.
  • 동일한 값이 여러번 삽입 되면 하나의 값만 저장됩니다.
• Fast Lookup이 필요할때 주로 쓰입니다.
• Set이라는 인터페이스를 통해 자바에서는 3가지의 Set이 있다.일반적으로 HashSet, TreeSet, LinkedHashSet 순으로 빠르다.
  1. Hash 알고리즘을 이용한 HashSet
  2. 이진 탐색 트리를 사용하여 오름차순 정렬까지 해주는 TreeSet
  3. Set에 순서를 부여해주는 LinkedHashSet