[자료구조/Data Structure] 선형 자료구조 Array / LinkedList / Stack / Queue

Array

[출처 : brilliant.org]

번호(인덱스)와 번호에 대응하는 데이터들로 이루어진 자료 구조

특징

• 논리적 저장순서와 물리적 저장순서가 일치
• 데이터를 물리적 주소에 순차적으로 저장

장점

• 데이터의 참조가 쉽다.
  
  • 인덱스로 바로 접근 가능 : O(1)
• 빠른 접근 속도
  
  • random access(비순차적 접근)이 가능

단점

• 배열의 길이가 정해져 있다.
  
  • 자원을 미리 할당 받기 때문에 사용하지 않는 불필요한 공간이 낭비됨
• 메모리 삽입/삭제가 번거롭다.
  
  • 삽입/삭제 시 배열의 빈 공간을 생성/제거하기 위해 나머지 원소들을 shift 해야함 : O(n)

Array와 List 차이 (자세한 내용)

List는 순서가 있는 빈틈 없는 데이터의 모임이다.
따라서, 빈 엘리먼트를 허용하느냐가 가장 큰 차이이다.
데이터 개수가 정해져있고 자주 사용된다면 가벼운 array를 사용하는 것이 좋다.

---

 

Linked List

[출처 : wikipedia.org]

 

각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조

특징

• 각 노드는 자신의 value와 다음 노드의 주소를 기억
• Array의 단점을 극복하기 위해 만들어짐

장점

• 삽입/삭제가 용이하다.
  
  • 새로운 노드 생성/삭제 후 이전 노드의 주소만 변경해주면 됨 : O(1)
  • 크기가 유동적이다.
• 삭제시 불필요한 공간이 생성되지 않는다.
• 자원을 미리 할당받지 않으므로 쉽게 크기를 늘릴 수 있다.

단점

• 접근 속도가 떨어진다.
  
  • 첫번째 노드부터 특정 노드까지 링크를 따라가며 탐색 : O(n)
  • 따라서, 원하는 위치에 삽입/삭제 할 경우 O(n)의 시간이 추가로 걸림
• 포인터 공간이 하나 이상 추가되어 메모리가 크다.
  
  • 메모리 할당/삭제로 인한 성능 저하
  • 삽입/삭제 시마다 메모리를 할당/삭제하게 되어 미리 할당받는 배열에 비해 성능이 저하됨

종류

단일 연결 리스트	이중 연결 리스트	원형 연결 리스트
[출처 : wikimedia.org]	[출처 : wikimedia.org]	[출처 : wikimedia.org]
하나의 포인터 공간 포인터는 다음을 가르킴	두개의 포인터 공간 각 포인터는 앞,뒤를 가르킴	하나의 포인터 공간 마지막이 앞을 가르킴

---

 

Stack

[출처 : wikimedia.org]

특징

• LIFO(후입선출) : 나중에 들어간 원소가 먼저 나온다.
• 리스트의 한쪽 끝으로만 자료의 삽입/삭제가 이루어짐

연산

• push() : 상단에 데이터를 추가한다.
• pop() : 가장 위에 있는 데이터를 삭제한다.
• empty() : 비어있으면 참, 아니면 거짓.
• top(): 가장 위에 있는 데이터를 반환한다.

용도

• 서브 프로그램 호출시 복귀주소를 저장할 때
• 함수 호출 순서를 제어할 때
• 인터럽트가 발생하여 복귀주소를 저장할 때
• 후위표기법으로 산출된 산술식을 연산할 때
• 0 주소 지정방식 명령어의 자료 저장소
• 재귀 프로그램(Recursive Program)의 순서를 제어할 때
• 컴파일러를 이용한 언어 번역 시

JAVA

• 클래스로 제공
• List 컬렉션 클래스의 Vector을 상속받아, 전형적인 스택 메모리 구조의 클래스를 제공

+ StackOverFlow란?
간단하게, 사용가능한 메모리가 더이상 없다는 뜻
스택(=사용가능한 메모리 용량)이라고 생각하고 그 범위를 넘어섰다는 뜻이다.

---

Queue

[출처 : computersciencewiki.org]

특징

• FIFO(선입선출) : 먼저 들어간 원소가 먼저 나온다.
• 리스트의 한쪽 끝에서는 삽입만, 나머지 끝에서는 삭제만 이루어짐

연산

• enqueue() : 뒤에 데이터를 추가한다.
• dequeue() : 앞에 데이터를 삭제한다.
• empty() : 비어있으면 참, 아니면 거짓.
• peek() : 맨 앞 요소를 반환한다.

종류

• 선형
  
  • 막대 모양으로 된 큐로, dequeue로 인해 생긴 빈 공간이 생긴다.
  • 빈 공간을 사용하기 위해선 모든 없애거나 한칸씩 이동해야 한다.
• 원형
  
  • 원형으로 연결한 큐로, 선형 큐의 문제점을 해결
  • 끝 부분을 앞 빈 공간과 연결시켜 데이터를 추가해 나가는 방식
• 리스트
  
  • 길이를 쉽게 늘릴 수 있어 오버플로우 발생 X, 삽입과 삭제 제한 X
  • 단, 원형 큐에 비해 성능이 떨어짐.

용도

• 순서를 기다리는 류의 프로세스 처리
  
  • 예) 대기행렬
• 운영체제의 작업 스케줄링

JAVA

• 인터페이스 형태로 제공
• Queue 인터페이스를 상속 받는 하위 인터페이스 4가지가 있음. (Deque 등)
  즉, Queue 인터페이스를 직간접적으로 구현한 클래스가 많음
  
  • LinkedList : Deque인터페이스를 구현

우선순위 큐 (Priority Queue)

보통의 큐에서 우선 순위가 더해진 자료구조

• 새 요소에 우선순위를 부여해서 큐에 삽입
• 가장 높은 우선 순위를 갖는 요소부터 빠져나오도록 함

연산

• insert_with_priority : 새 원소에 우선순위를 지정하여 큐에 추가
• pull_highest_priority_element : 가장 높은 우선순위를 가진 원소를 제거

---

Reference

• Interview_Question_for_Beginner 자료구조
• Array & LinkedList
  
  • 배열리스트와 링크드리스트의 차이
  • 배열과 연결리스트
  • 연결리스트 wiki
• Stack & Queue
  
  • JAVA Stack&Queue
  • 스택, 큐의 용도
  • 스택 wiki
  • 큐 wiki
  • 우선순위 큐 wiki

wiki

• 우선순위 큐 wiki