배열,리스트,스택,큐

이신필·2022년 1월 18일
리스트배열선형자료구조스택자료구조큐
0

자료구조

목록 보기
1/1
post-thumbnail

배열,리스트,스택,큐

선형 자료 구조

선형 자료 구조란 데이터 구조를 구성하는 요소들이 서로 인접하여 순차적인 방식으로 정렬 (이어져 있다는 뜻)되어 있음을 뜻한다. 가장 일반적인 선형 자료구조인 배열, 리스트에 대해 알아보자

배열

이미지 출처: TCP SCHOOL

연관된 데이터들을 그룹으로 관리하기 위한 자료구조로 자료형들이 메모리 공간상에서 연속적으로 저장되어 있는 구조이다. 때문에 물리적 저장공간과 논리적 저장공간이 같고, 각각의 요소 들에 인덱스 가 붙어있다.

  • 인덱스를 통해서 데이터에 바로 접근 가능하다. (랜덤 엑세스)

    Random access(임의 접근): 메모리 주소만 있어도 즉시 데이터를 읽을 수 있는 호출 방식
    Sequential access (순차 접근): 데이터의 위치까지 맨앞부터 차례로 탐색하는 방식

  • 데이터를 추가하거나 삭제 할 때 배열 내 다른 데이터의 순서를 다시 매겨야 한다.
  • 크기가 고정되어있다.
  • 1차원 배열부터 다차원 배열까지 구성이 가능하다.
  • Cache hit 가능성이 커져 성능에 큰 도움이 된다

    CPU가 참조하고자 하는 메모리가 캐시에 존재하고 있을 경우 Cache Hit라고 한다.

  • 각 기능별 복잡도

리스트

배열이 가지고 있는 인덱스라는 장점을 버리고 빈틈없는 적재라는 장점을 취한 자료구조이다. 노드(node)라고 불리는 리스트의 요소들은 데이터 요소와 포인터의 쌍으로 구성된다. 각 노드들은 흩어진 상태로 저장이 되고, 각 노드에 접근시 이전 요소의 포인터를 사용하여 접근한다.

이미지 출처: TCP SCHOOL

  • 해당 리스트에 진입하는 첫 노드 지점을 헤드라고 한다
  • 노드 하나가 다음노드의 포인터 하나만 갖는 유형이 단반향 연결 리스트
    • 마지막 노드는 보통 null 값을 가지게 된다.
  • 노드 하나가 이전노드, 다음노드의 포인터 모두 갖는 유형이 양방향 연결 리스트
    • 단방향에 비해 삭제할 때나 양방향 순회시 더 효율적
  • 순차성을 보장하지 못하기 때문에 Spatical locality 보장이 되지 않아 cache hit 가 어렵다.

    Spatical locality: 최근 접근했던 주소 근처의 주소들을 접근하는 경향을 말함

  • 순환 연결 리스트(circular linked list)
    • 모든 노드들이 원형으로 연결됨, 마지막 노드가 첫 번째 노드와 연결됨
    • 단방향 또는 양방향 모두 가능
  • 각 기능별 복잡도

스택

이미지 출처: programiz

추가된 요소를 메모리의 가장 앞 주소에 배치하는 자료구조 요소를 스택의 최상단에서만 삭제 및 추가할 수 있다. 마지막에 넣은 요소가 제일 먼저 나오기 때문에 LIFO(Last In First Out) 후입선출이라 한다.

  • 스택에 요소를 추가하는 동작을 push 라 한다
  • 스택에 요소를 삭제할 때 가장 마지막으로 추가된 요소를 삭제는 동작을 pop 이라 한다.
  • 크기를 늘릴 수 있는지 여부에 따라 정적 스택(배열이용)과 동적 스택(리스트이용)으로 구분
  • 함수 호출, 스케줄링 등 다양한 부분에서 사용됨
  • 각 기능별 복잡도

큐

이미지 출처: programiz

각 요소에 우선순위를 부여하는 자료 구조, 먼저 추가된 요소가 우선적으로 삭제된다는 점에서 FIFO(First in First out ) 선입선출이라 한다.

  • 큐 맨 뒤쪽에 요소를 추가하는 동작을 enqueue 라 한다.
  • 큐에서 가장 오랫동안 있던 요소가 먼저 삭제되고, 그 동작을 dequeue 라고 한다.
  • 우선순위큐
    • 큐에 모든 요소에는 우선순위가 있으며 우선순위가 높은 요소는 우선순위가 낮은 요소보다 먼저 삭제된다.
  • 각 기능별 복잡도

참고자료

profile
이신필

0개의 댓글