Stack Queue / Array와 linked List

마동찬·2023년 7월 27일

📌 Stack과 Queue

Stack : 마지막에 저장한 데이터를 가장 먼저 꺼내는 LIFO(Last-In-First-Out)인 자료구조

Queue : 먼저 들어간 데이터를 먼저 꺼내는 FIFO(First-In-First-Out)인 자료구조

Stack

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

stack.push(1);
stack.push(2);
stack.peek(); // 2를 return , stack = [1, 2]
stack.pop(); // 2를 return  , stack = [1]

push(object item) : Stack에 객체(item) 저장
peek() : Stack에 맨 위의 저장된 객체를 반환, 객체를 꺼내지는 않음(Stack에 비어 있을 경우EmptyStackException발생)
pop() : Stack의 맨 위에 저장된 객체를 반환, 객체를 꺼냄 (Stack에 비어 있을 경우 EmptyStackException발생)
isEmpty() : Stack이 비어있는지 boolean값으로 반환

Queue

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

queue.offer(1);
queue.offer(2);
queue.peek(); // 1를 return, queue = [1,2]
queue.poll(); // 1를 return  , queue = [2]

offer(object item) : Queue에 객체(item) 저장
peek() : Queue에 맨 위의 저장된 객체를 반환, 객체를 꺼내지는 않음(Queue가 비어 있을 경우 null 반환)
pop() : Queue의 맨 앞에 저장된 객체를 반환 (Queue가 비어 있을 경우 null 반환)
isEmpty() : Queue이 비어있는지 boolean값으로 반환

📌 Array와 Linked List

📑 ArrayList의 문제점

ArrayListVisit Website는 배열 공간(capacity)가 꽉 차거나, 요소 중간에 삽입을 행하려 할때 기존의 배열을 복사해서 요소를 뒤로 한칸씩 일일히 이동해야 하는 작업이 필요하다.

이러한 부가적인 연산은 시스템의 성능 저하로 이어져 삽입 / 삭제가 빈번하게 발생하는 프로세스의 경우 치명적일 수 있다. 그리고 자료들이 지속적으로 삭제되는 과정에서 ArrayList에서는 그 공간 만큼 낭비되는 메모리가 많아지게 되고 또한 리사이징 처리에서 시간이 소모된다.

📑 LinkedList의 장단점

반면, LinkedListVisit Website는 불연속적으로 존재하는 데이터를 서로 연결(link)한 형태로 구성되어있기 때문에 공간의 제약이 존재하지 않으며, 삽입 역시 노드가 가리키는 포인터만 바꿔주면 되기 때문에 배열처럼 데이터를 이동하기 위해 복사하는 과정이 없어 삽입 / 삭제 처리 속도가 빠르다. 따라서 삽입 / 삭제가 빈번하게 발생하는 프로세스의 경우 LinkedList를 사용하여 시스템을 구현 하는것이 바람직하다

하지만 LinkedList 에도 만능이 아니며 단점이 존재한다.

요소를 get 하는 과정에서 ArrayList와 굉장한 성능 차이를 보이는데, ArrayList에서는 무작위 접근(random access)이 가능하지만, LinkedList에서는 순차접근(sequential access) 만이 가능하기 때문이다.

예를 들어 n개의 자료를 저장할 때, ArrayList는 자료들을 하나의 연속적인 묶음으로 묶어 자료를 저장하는 반면, LinkedList는 자료들을 저장 공간에 불연속적인 단위로 저장하게 된다.

이를 그림으로 표현하자면, 아래 빌딩 그림을 메모리(RAM)으로 비유하고 각기 방을 데이터라고 비유하자면, ArrayList는 연속적인 묶음으로 되어있지만, LinkedList는 각기 다른 방에 저장되어있고 링크로 연결되어 있음을 볼 수 있다.

그래서 LinkedList는 메모리 이곳저곳에 산재해 저장되어 있는 노드들을 접근하는데 있어 ArrayList보다 당연히 긴 지연 시간이 소모되게 된다. 특히 Singly Linked List는 단방향성만 갖고 있기 때문에 인덱스를 이용하여 자료를 검색하는 애플리케이션에는 적합하지 않는다.

LinkedList의 또 다른 단점은 참조자를 위해 추가적인 메모리를 할당해야 하는 점 이다. 배열 같은 경우 그냥 데이터 그대로만 저장하면 되지만, LinkedList의 노드 같은 경우 데이터 이외에 next 나 prev 같은 참조자도 저장해야 되기 때문에 추가적인 공간이 더 필요 할 수 밖에 없다.

📑 LinkedList vs ArrayList 성능 비교

👉 시간 복잡도 비교

LinkedList를 처음 배우는 새내기들이 착각하는 것이, 요소를 추가하는 것과 요소를 삭제하는 것의 시간복잡도가 오로지 O(1) 이라는 점이다. 맨 앞이나 맨 뒤 요소만 추가하고 삭제한다고 가정하면 시간복잡도는 O(1)이 맞지만, 중간에 요소를 추가 / 삭제 한다면 그 중간 위치까지 탐색을 해야 하므로 최종적으로 O(N)이 된다.