ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 자료구조 복습하기
    CS지식/자료구조 2021. 12. 24. 22:55

    1. array vs linkedlist

    array는 데이터를 저장할 수 있는 자료구조로 특징으로는 논리적인 저장순서와 물리적인 저장 순서가 일치한다는 것
    조금 더 자세히 설명하면, array에 0, 1, 2 순서대로 저장되어있으면 실제 메모리에 저장된 것도 0, 1, 2가 순서대로 저장되어 있고 주소도 순차적임
    시간복잡도를 얘기하면 인덱스를 알고 있다면 O(1)로 탐색이 가능하고 삭제, 삽입 연산의 경우, 맨 끝 원소는 O(1)이고 다른 위치 원소의 경우에는 원소의
    위치를 옮기는 작업이 필요하므로 O(n)

    linked-list도 array처럼 데이터를 저장할 수 있는 자료구조로 특징으로는 논리적인 저장순서와 물리적인 저장 순서가 일치할 수도 있고 안할 수도 있음
    linked-list는 node에 해당 element와 다음 element의 위치(주소)를 가지고 있고 탐색을 할 경우에 목표 element를 찾기 위해서 처음부터 순자적으로 접근해야하기 때문에
    O(n) 시간복잡도를 가지고 있음
    삽입, 삭제 연산의 경우에는 첫 원소에 대한 연산은 O(1), 첫 원소가 아닌 다른 원소에 대한 연산은 위치를 찾아야하는 연산이 필요하기에 O(n)

     

     

    2. stack vs queue

    stack은 나중에 들어온 데이터가 먼저 나가는 LIFO 구조로 push라는 연산을 통해 데이터를 삽입하고 pop이라는 연산을 통해 데이터를 삭제할 수 있는 자료구조
    queue는 먼저 들어온 데이터가 먼저 나가는 FIFO 구조로 enqueue라는 연산을 통해 데이터를 삽입하고 dequeue라는 연산을 통해 데이터를 삭제할 수 있는 자료구조

    스택의 활용사례는 웹 브라우저에서 뒤로가기 기능을 위해 방문기록을 저장할 때 사용할 수 있고 큐는 버퍼나 작업 스케쥴링에 사용

     

    ps) 원형 큐: 선형 큐의 단점을 보완하기 위해서 개발됨, 모듈러 연산 (rear + 1) % (큐 크기)로 큐가 꽉차있거나 텅 비어있는 것을 판단

     

     

    선형 자료구조 vs 비선형 자료구조
    선형 자료구조는 하나의 자료 뒤에 하나의 자료가 존재하는 것이고 비선형 자료구조는 하나의 자료 뒤에 여러개의 자료가 존재할 수 있는 것이다.

    추상자료형(ADT)?
    세부 구현으로부터 분리해 핵심 개념이나 기능을 간추려 낸 자료형으로 구현 내용은 명시하지 않고 인터페이스만 제공

     

    댓글

Designed by Tistory.