자료구조
컴퓨터 과학에서 효율적인 접근 및 수정을 가능하게 하는 자료의 조직
-> 개발자의 부담을 줄여줌
선형 자료구조
- 하나의 자료 뒤에 하나의 자료가 존재하는 구조
즉, 자료들 간의 관계가 1대1 인 자료구조 - 배열, 리스트, 스택, 큐, 덱 등
비선형 자료구조
- 하나의 자료 뒤에 여러개의 자료가 존재할 수 있는 구조
즉, 자료들 간의 관계가 1대 N 혹은 N:M 인 자료구조 - 계층적 구조를 나타내기에 적합
- 트리, 그래프 등
배열
정적 배열
int arr = new int[10];
배열은 선언하게 되면 연속적인 메모리 공간을 차지하게 됩니다.
동적 배열
List<Integer> arr = new ArrayList<>();
동적 배열은 내부 필드로 정적 배열을 가지고 있고, 동적으로 사이즈를 조절해 주는 배열입니다. 처음 생성할 때 기본 사이즈는 10으로 할당되고, 요소를 하나 추가할 때 마다 사이즈가 1 또는 현재 사이즈의 절반만큼 늘어나게 됩니다.
arr.add(n); 명령어로 배열의 맨 끝에 n을 추가할 수 있습니다.
arr.get(i); 명령어로 i번 째 인덱스에 해당하는 값을 조회할 수 있습니다.
arr.set(i,n); 명령어로 i번 째 인덱스에 해당하는 값을 n으로 변경시킬 수 있습니다.
arr.remove(i); 명령으로 i번 째 인덱스의 데이터를 삭제할 수 있습니다.
배열은 조회를 인덱스를 통해서 하므로 시간복잡도가 O(1) 이지만, 삽입 삭제의 경우 배열을 다시 생성해 주기 때문에 O(N)의 시간복잡도를 가집니다.
연결 리스트
LinkedList<Integer>() = new LinkedList<>();연결리스트는 노드들이 앞 뒤로 연결되어 있는 선형 자료구조 입니다.
연결리스트는 삽입, 삭제의 경우 O(1)의 시간복잡도,
조회, 수정의 경우 O(N)의 시간복잡도를 가집니다.
삽입 삭제의 경우 해당 위치에서 앞 뒤 노드만 처리해주면 되기 때문에 빠르게 처리 가능하지만, 조회 또는 삭제의 경우 해당 노드의 위치를 앞에서부터 순차적으로 찾아야하기에 O(N)의 시간복잡도가 소요됩니다.
삽입, 삭제
1 -> 2 -> 3 -> 4 -> 5
이렇게 연결 리스트가 구성되어 있다면, 3을 삭제하는 방법은
2의 뒤에 4를, 4의 앞에 2를 연결해주면
1 -> 2 -> 4 -> 5
이렇게 삭제 시킬 수 있고,
삽입하는 방법도 동일하게
1 -> 2 -> 6 -> 4 -> 5
이런 방식으로 삽입할 수 있습니다.
연결리스트를 활용하여 구현된 자료구조에는 스택, 큐, 덱 등이 있습니다.
스택, 큐, 덱은 연결리스트를 활용하여 구현하였기에 삽입 삭제가 빠르고, 조회 수정이 느립니다.
스택
Stack<Integer>() = new Stack<>();스택은 FILO(First In Last Out) 선입 후출의 구조로 처음 깐 접시는 맨 마지막에 뺄 수 있는것 처럼 먼저 들어간 데이터는 맨 마지막에 빼낼 수 있는 구조입니다.
stack.push();
- push메소드를 통해 데이터를 스택에 쌓을 수 있습니다.
stack.pop();
- pop을 통해 맨 위 데이터를 뽑아낼 수 있습니다.
stack.peek();
- peek을 통해 맨 위 데이터를 조회할 수 있습니다.
큐
Queue<Integer>() = new LinkedList<>();큐는 FIFO(First In First Out) 선입 선출의 구조로 터널에 자동차들이 들어가고 나올 때 들어간 순서대로 나가는 것 과 같은 구조입니다.
queue.add();
- add를 통해 데이터를 큐의 맨뒤에 추가할 수 있습니다.
queue.poll(); - poll을 통해 큐 맨 앞 데이터를 꺼낼 수 있습니다.
queue.peek(); - peek을 통해 큐 맨 앞 데이터를 조회할 수 있습니다.
덱
Deque<Integer> deque = new LinkedList<>();덱은 스택 + 큐 형태의 자료구조 입니다.
앞뒤 둘다 삽입 삭제가 가능합니다.
deque.addFisrt();
deque.addLast();
- 덱 앞 또는 뒤에 데이터를 추가합니다.
deque.PollFirst();
deque.PollLast();
- 덱 앞 또는 뒤 데이터를 꺼낼 수 있습니다.
deque.peekFirst();
deque.peekLast();
- 덱 앞 또는 뒤의 데이터를 조회할 수 있습니다.
