Data Structure: Stack, Queue, Linked list

minjae-mj·2020년 10월 28일
0

 🍉   Learning Journal

목록 보기
19/26
post-thumbnail

여기 소개하는 세 가지 자료구조는 모두 선형적인 데이터 구조를 가진다. 길게 쭉 뻗은 소나무처럼 긴~ 테이블을 생각해보자.

🙋🏻‍♀️ Stack 이 뭐예요?

선반 위에 쌓여있는 접시를 떠올리면 쉽다. 마지막에 온 게 가장 먼저 빠진다. (Last In, First Out) 아래 실생활 사례 참고!

  1. 프로그래밍 언어의 런타임에서 함수 호출 관리
  1. 실행취소(undo)
  2. 노래 플레이리스트
  3. 인터넷창 뒤로가기
  4. TV 이전화면

🙋🏻‍♀️ Queue 는 뭐예요?

역시 선형적인 데이터 구조를 가지는데, 차이점은 선입선출! 먼저 온 순서대로 빠진다. 은행에서 번호표 뽑고 차례대로 대기하는 것처럼. (First In, First Out)

  1. node.js 런타임에서 이벤트 큐
  1. 메세지 큐
  2. 메세지 브로커
  3. Tree 또는 Graph 구조의 데이터 자료 탐색 시 너비우선탐색 (BFS)
  4. 키보드 입력

🙋🏻‍♀️ Linked list 는 뭐예요?

연결리스트에서 노드들은 1) 데이터 2) 포인터 로 구성되어 있다. 포인터라 함은 노드A 가 노드B를 가리키고 있다고 보면 된다. 이 포인터를 통해 각 노드들이 연결되어 있다.

  1. Singly linked list
    노드가 다음 노드만 가리킬 때. 어릴 때, 앞사람 어깨에 손을 얹고 꼬리물기 게임하던 것 같은 형태를 가진다. 한 사람 한사람이 노드이고, 내가 얹은 손은 포인터! 그래서 포인터가 한 쪽만 가리킨다.

  2. Doubly linked list
    노드가 이전 노드와 다음 노드 모두 가리킬 때. 체육 시간인데, 양 옆 사람과 손을 잡고 있다고 생각해보자. 즉 포인터가 양 방향을 가리킨다.

만약 내가 중간에 있는 노드인데 연결리스트 밖으로 빠지고 싶다면, 내가 빠지면서 이전에 있던 친구 손을 내 다음 친구 손과 연결시켜 주기만 하면 된다. 다시 말해, 데이터의 삽입과 삭제가 빈번히 일어날 경우에 강점이 있는 자료 구조다.

파일시스템 관리

0개의 댓글