[CS] 자료구조

Array

연속된 자료를 다룰때 가장 간단히 사용할 수 있는 자료구조이다.

+ 인덱스를 통한 Random Access가 가능하다 -> 검색에 적합

- 중간에 값을 추가하거나 제거하는 과정에서는 다른 element들을 shift해주는 비용이 들어 비효율적이다.

- 처음 생성할 때의 크기와 타입이 고정이기 때문에 데이터가 늘어나거나 최대 사이즈를 알 수 없을 때 부적합하다.

Array는 선언시 컴파일타임에 Stack 섹션에 메모리할당이 된다.

 

ArrayList

array를 보완한 것으로 크기를 정해주지 않아도 된다.

용량을 초과하면 더 큰 용량의 배열로 복사하는 grow 작업을 한다.

 

LinkedList

+ 필요할 때마다 메모리를 동적으로 할당하기 때문에 효율적이다.

+ 각 노드들이 자기 자신 다음에 어떤 원소인지만을 기억하고 있어서 중간에 값을 추가하고 제거할 때 이 부분만 바꾸어주면 된다.

- 특정 element에 접근하기 위해서는 처음부터 element에 도착할 때까지 순차적으로 검색하면서 찾아야한다.

LinkedList는 런타임에 Heap 섹션에 메모리할당이 된다.

---

Stack

선형자료구조이다.

한 쪽 끝에서만 자료를 넣고 뺄 수 있고 마지막에 들어간 element가 먼저 나오는 구조(LIFO)이다. 중간의 데이터는 알 수 없다.

사용사례) 재귀 알고리즘, 뒤로가기, 실행 취소(undo), 역순 문자열 만들기

스택 구현

//연결 리스트로 사용 할 노드 class
public class Node {
	private Object data;
	private Node nextNode;
}	

public Node(Object data){
	this.data = data;
	this.nextNode = null;
}

//해당 노드를 원하는 노드(Node top)와 연결해주는 메소드
public void linkNode(Node top){
	this.nextNode = top;
}


//해당 노드의 데이터를 가져오는 get메소드
public Object getData(){
	return this.data;
}

//해당 노드와 연결된 노드를 가져오는 get메소드
public Node getNextNode(){
	return this.nextNode;
}

public class ListStack {
	private Node top;
	public ListStack(){
		top = null;
	}

	public boolean isEmpty(){
		return (top==null);
	}

	public void push(Object item){
		Node newNode = new Node(item);
		newNode.linkNode(top);
        top = newNode;
	}
    
	public Object peek(){
		return top.getData();
	}

	public Object pop(){
		if(isEmpty()) throw new ArrayIndexOutOfBoundsException();
        else{
        	Object item = peek();
            top = top.getNextNode();
            return item;
		}
	}
}

public class ArrStack {

	private int top; //마지막 위치 (삽입,삭제가 이루어질 위치)
	private int maxSize;
	private Object[] stackArray;

	//생성자 : 프로퍼티 초기
	public ArrStack(int size){
		this.top = -1;
		this.maxSize = size;
		this.stackArray = new Object[maxSize];
	}

	//스택이 비어있는지 확인
	public boolean isEmpty(){
		return (top==-1);
	}

	//데이터 삽입
	public void push(Object item){
		//스택에 가득찼을 때 예외처리
		if(top >= maxSize-1) throw new ArrayIndexOutOfBoundsException((top+1)+">="+maxSize);
		stackArray[++top] = item;
	}

	//데이터 읽기
	public Object peek(){
		//스택이 비어있을 때 예외처리
		if(isEmpty()) throw new ArrayIndexOutOfBoundsException(top);
		return stackArray[top];
	}

	//데이터 삭제 : 삭제된 데이터 반환(백업용도)
	public Object pop(){
		Object item = peek();
		top--;
		return item;
	}
}

 

Queue

선형자료구조이다.

먼저 들어간 element가 먼저 나오는 구조(FIFO)이다.

사용사례) 버퍼, BFS

---

Priority Queue

elemenet들이 우선순위를 가지고 있고 우선순위가 높은 데이터가 먼저 나오는 구조

배열, 연결리스트, heap으로 구현하는데 heap이 가장 효율적이다.

사용사례) 작업스케쥴링

 

Heap

완전 이진 트리의 일종으로 Priority Queue를 위하여 만들어진 구조이다.

중복된 값을 허용하며 부모 노드의 키 값이 자식 노드보다 항상 크거나 작은 이진 트리이다.

여러 값들 중 최대값이나 최소값을 빠르게 찾아낸다.

---

Tree

계층적 관계를 표현하는 비선형 자료구조이다.

사이클이 없는 하나의 연결 그래프이다.

 

구성요소: 노드, 간선, 루트노드, 리프노드, 내부노드(루트노드포함)

이진트리: 루트 노드를 중심으로 두개의 서브 트리로 나누어지며, 나누어진 서브 트리들도 모두 두개의 서브트리로만 이루어지는 트리 (공집합 포함)

종류: 정이진트리(자식노드가 0 or 2), 포화이진트리(완전히 꽉참), 완전이진트리(상->하, 좌->우 순서로 채워짐), 

 

Binary Search Tree

이진트리의 일종으로 효율적인 탐색을 할 수 있게 해준다.

트리가 불균형하다면 시간복잡도가 늘어난다.

 

• 노드에 저장된 key는 유일하다 (중복X)
• 부모의 키가 왼쪽 자식 노드의 key보다 크다
• 부모의 키가 오른쪽 자식 노드의 key보다 작다
• 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다.

---

Hash table

hash fuction을 통한 hash value와 data를 1:1로 저장하는 자료구조

Hash function : 데이터를 효율적으로 관리하기 위해, 다양한 길이 데이터(key)를 고정된 길이의 데이터(hash value)로 매핑하는 함수

Hashing : 원래 데이터 값(key)을 해시 값(hash value)로 매핑하는 과정

해시 사용 예) 비밀번호 저장, 복제문서인지 판별, 검색용도

+ 적은 자원으로 많은 데이터를 효율적으로 관리 가능 – 고정된 길이 해시 값

+ 데이터 검색 속도가 빠름 - Array O(N), BST O(logN), Hash table O(1) 데이터 충돌시 O(N)

- 상하관계, 순서가 있는 배열에는 어울리지 않음

- 공간 효율성이 떨어짐 (부족 or empty) -> 해시테이블 key 보다 적게 운용

- Hash function의 의존도가 높음

 

데이터가 많아지면 다른 키에 대해 같은 해시 값을 가지는 Collision이 발생한다. 따라서 해시 충돌을 최대한 줄이는 해시함수를 만드는 것이 중요!

collision 현상을 해결하는 방법

1. 체이닝: 연결리스트로 노드를 계속 추가해나가는 방식 (제한 없이 계속 연결 가능, but 메모리 문제)
2. Open Addressing: 해시 함수로 얻은 해시값이 아닌 다른 주소에 데이터를 저장할 수 있도록 허용 (해당 키값에 저장되어있으면 다음 주소에 저장)

---

B-Tree

하나의 노드에 여러 key, data를 가지는 트리구조

데이터베이스, 파일 시스템에서 널리 사용된다. (B+*tree로 발전)

+ 삽입, 삭제 후에도 균형 트리 유지 → 균등한 응답속도 보장

- 삽입, 삭제 시 균형을 유지하기 위한 복잡한 연산 필요

- 순차 접근시 inorder 순회로 비효율적

 

B+Tree

Not Leaf 노드들은 인덱스 역할만 한다.

B-Tree와 유사하지만 리프노드가 연결리스트의 형태를 띄어 선형 검색이 가능

모든 key, data가 리프노드에 모여있음.

실제 DB의 인덱싱에 사용

+ 순차 접근 용이

- B-Tree의 경우 best case에는 루트에서 끝날 수 있지만, B+Tree의 경우 무조건 Leaf까지 가야함

- index와 data간의 중복성 존재

※ Hash는 O(1)인데 왜 인덱싱에 B+Tree를 사용할까?
Hash - 단하나의 데이터를 탐색하는 시간에만 O(1) but, DB에서는 등호(=) 뿐 아니라 부등호(<. >) 사용가능
Hash는 정렬 X -> 찾을 수 없음

※ 다른 Balanced Tree도 많은데?
노드에 여러 data를 저장하기 때문에 포인터 접근 수를 줄여서 가장 최적!
데이터 탐색 뿐 아니라, 저장, 수정, 삭제에도 항상 O(logN)의 시간 복잡도를 가짐.