선형(Linear) 자료구조

사한·2023년 11월 26일

Java 선형자료구조 시간복잡도 자료구조 자바

안녕하세요 사한입니다~
오늘은 선형 자료구조에 대해서 이야기 해보려합니다! 😙
이 포스팅은 자바 언어를 기준으로 이야기 하고있음을 미리 밝히겠습니다~😎

선형(Linear) 자료구조

선형 자료 구조란?

자료들간의 앞뒤 관계가 1 : 1 인 구조를 이야기합니다.

그러면 반대로 비선형 자료 구조는?

자료들간의 앞뒤 관계가 1 : n 또는 n : n 인 구조를 이야기합니다.

이러한 선형 자료구조의 종류 5가지를 순서대로 이야기 해보겠습니다.

배열
연결 리스트
큐
스택
덱

해당 순서로 진행 됩니다!

배열

배열을 다음과 같은 특징을 가지고 있습니다.

일렬로 늘어선 같은 종류의 자료 여러개를 저장한다.
연속적인 메모리 공간 차지한다.

이러한 배열은 정적 배열과 동적 배열로 구분됩니다.

정적 배열

배열의 크기가 고정적이다.
배열을 선언할 때 크기를 지정하고 이후엔 크기를 변경할 수 없다.

실제 사용 예시)

int[]  num = new int[5];

동적배열

동적으로 배열의 크기를 조절한다.
배열을 조정하며 요소를 추가, 제거, 접근 등의 기능을 제공한다.

실제 사용 예시)

ArrayList<Integer> arrayList = new ArrayList<>();

동적 배열은 어떻게 배열의 크기를 동적으로 조절할까?

내부에 정적배열이 선언되어있고 크기가 변경 될 때 새 배열을 선언한뒤 기존 원소들을 복사하여 새 배열로 옮기고 있다!
가끔 일반배열을 쓰다가 동적배열로 교체했다고 느려지면 동적배열의 사이즈 문제일수도 있다.
배열의 최종크기를 알고 있다면 자바의 ensureCapacity()로 동적배열의 사이즈를 미리 늘려 두어서 최적화가 가능하다!

다음으로는 동적배열의 장점과 단점을 알아보겠습니다.

장점

인덱스를 통해 접근하기 때문에 조회가 빠르다.

단점

값 삽입과 제거할때 배열을 다시 선언 하기때문에 느리다.

마지막으로 동적 배열의 메서드 예시와 시간 복잡도 표입니다.

        ArrayList<Integer> arrayList = new ArrayList<>();  
        arrayList.add(1);  
        arrayList.remove(0);  
        arrayList.get(0);  
        arrayList.contains(1);  
        arrayList.size();

Type	Add	Remove	Get	Contains	Size
ArrayList	O(1)	O(n)	O(1)	O(n)	O(1)

연결 리스트

연결 리스트는 다음과 같은 특징을 가지고 있습니다.

배열 원소들의 순서를 유지하면서 연속된 공간에 데이터를 저장하지 않는다.
연결 리스트는 노드로 이루어져있다.
노드는 요소의값과 다음노드와 이전노드를 참조하고 있다.

실제 사용 예시)

LinkedList<Integer> linkedList = new LinkedList<>();

다음으로는 연결 리스트의 장점과 단점을 알아보겠습니다.

장점

값 삽입과 제거 시 해당 노드의 앞, 뒤 노드의 참조만 변경하면 되기때문에 속도가 빠르다.

단점

특정값을 찾기 위해서 노드를 따라가며 순회 해야해서 속도가 느리다.

마지막으로 연결 리스트의 메서드 예시와 시간 복잡도 표입니다.

        LinkedList<Integer> linkedList = new LinkedList<>();
        linkedList.offer(1);
        linkedList.peek();
        linkedList.poll();
        linkedList.remove();
        linkedList.size();

Type	Offer	Peek	Poll	Remove	Size
LinkedList	O(1)	O(1)	O(1)	O(1)	O(1)

큐

큐를 이야기 할때 스택과 덱을 빼고 이야기 하기 서운하죠!
이 세 자료 구조를 구분하는것은 어느 쪽 끝에서 자료를 넣고 뺄 수 있는가 입니다.
큐를 비롯한 스택과 덱은 자료를 넣고 ,꺼내는 연산이 모두 상수시간 O(1)에 이루어져야 합니다.

스택과 덱의 특징은 조금뒤에 살펴보고 큐의 특징을 알아보겠습니다.

한쪽 끝에서 자료를 넣고 반대 쪽 끝에서 자료를 꺼낼 수 있다.
가장 먼저 들어간 자료를 가장 먼저 꺼내게 된다.(선입 선출, FIFO)

자바에서 큐는 어떻게 구현되어 있을까?

연결 리스트로 구현되어있다.
동적 배열을 통해서도 따로 구현할 수 있으나 보편적으로 사용하는 것은 연결리스트이다.

실제 사용 예시)

Queue<Integer> queue = new LinkedList<>();

마지막으로 큐의 메서드 예시와 시간 복잡도 표입니다.

        Queue<Integer> queue = new LinkedList<>();
        queue.offer(1);
        queue.peek();
        queue.poll();
        queue.remove();
        queue.size();

Type	Offer	Peek	Poll	Remove	Size
Queue	O(1)	O(1)	O(1)	O(1)	O(1)

스택

스택의 특징을 알아보겠습니다.

한쪽 끝에서만 자료를 넣고, 꺼낼 수 있다.
가장 늦게 들어간 자료를 가장 먼저 꺼내게 된다.(후입 선출, LIFO)

자바에서 스택은 어떻게 구현되어 있을까?

Vector를 통해 동적 배열로 구현되어 있다.
하지만 Vector를 통해 구현함으로써 생긴 단점 2가지가 존재한다.

Thread-safe 해서 멀티스레드 환경이 아닐 때 사용하면 lock을 거는 작업으로 많은 오버헤드가 발생한다.

Vector 클래스를 확장했기 때문에 LIFO 하지 못하게 데이터를 삽입, 삭제 가능하다.

따라서 Deque 인터페이스의 구현체인 ArrayDeque를 스택으로 사용하는 것이 좋다.

실제 사용 예시)

Stack<Integer> stack = new Stack<>();

마지막으로 스택의 메서드 예시와 시간 복잡도 표입니다.

        Stack<Integer> stack = new Stack<>();
        stack.push(1);
        stack.pop();
        stack.peek();
        stack.search(1);

Type	Push	Peek	Pop	search
Stack	O(1)	O(1)	O(1)	O(n)

덱(dequeue)

덱의 특징을 알아보겠습니다.

양쪽 끝에서 모두 자료를 넣고, 꺼낼 수 있다.
덱을 이용하면 스택과 큐 모두 구현할 수 있다.

자바에서 덱은 어떻게 구현되어 있을까?

연결 리스트와 동적 배열로 구현되어 있다.
보편적으로는 동적 배열로 구현된 클래스를 이용한다.

실제 사용 예시)

Deque<Integer> deque = new LinkedList<>(); // 연결 리스트로 구현된 클래스
Deque<Integer> arrayDeque = new ArrayDeque<>(); // 동적 배열로 구현된 클래스

마지막으로 덱의 메서드 예시와 시간 복잡도 표입니다.

        Deque<Integer> deque = new ArrayDeque<>();
        deque.peekFirst();
        deque.peekLast();
        deque.offerFirst(1);
        deque.offerLast(1);
        deque.pollFirst();
        deque.pollLast();
        deque.size();