Computer Science/자료구조

4. 리스트 ADT

2021. 5. 8. 17:41

리스트ADT

이번에는 리스트ADT를 알아볼겁니다. 

우선 ADT를 먼저 알아야합니다. 

추상자료형(ADT)이란 데이터구조의 추상형을 말한다고 하는데....조금 더 쉽게 말하자면 어떤 자료형이 있으면 그 자료형에 대한 연산을 명세한 것을 ADT라고 부르는 것입니다. 

 

따라서 다음을 명세한다고 정리할 수 있겠습니다 

1. 저장된 데이터

2. 데이터에 대한 작업들

3. 작업 중 발생 가능한 에러 상황들 

 

예를 들어서 주식거래 시스템 ADT를 짠다고 하면 

1. 데이터 : buy/sell 주문들 

2. 지원하는 작업들 

 buy, sell, cancel 등이 있을 수 있다.

3. 에러 상황들 : 존재하지 않는 주식에 대한 buy/sell 주문, 존재하지 않는 주문에 대한 cancel

 

정말 쉽게 얘기하자면

그리고 실제로 C언어를 공부하다보면 int, char, 포인터 이런 여러 자료형이 있잖아요? int 자료형 끼리는 +.-.*,/,% 이런 연산이 가능하고 포인터에서는 ++, -- 이러한 연산이 가능한 것 처럼 

우리가 자료형을 만든다면 이 자료형의 주제에 대한 연산도 있어야 한다는 겁니다. 

 

자료구조에는 여러가지 ADT가 있는데 그 중 대표적으로 리스트ADT가 있습니다. 

리스트ADT는 원소들의 순서집단을 저장하기 위한 "기초적인" 데이터구조입니다. 그래서 이 리스트를 활용해서 여러가지 자료구조를 또 만들 수 있어요

 

그리고 기본적인 메쏘드도 여러가지를 가지는데 

초기화, 삽입, 제거, 순회, get 그리고 에러상황들에 대한 예외들(부적합한 순위, 리스트 full, 비어있는 list)가 있습니다. 

 

이러한 리스트를 응용할 수 있는데 직접응용과 간접응용으로 나뉩니다. 

직접응용

 1. 스택 큐 집합 등을 표현하기 위한 도구 

 2. 소규모 데이터베이스 구축 

간접응용

 1. 복잡한 데이터구조 구축 재료 

이러한 스택과 큐를 연결리스트로 구현할 수 있습니다. 

 

그러면 이제 직접 리스트ADT를 구현하기 위해서 우리는 배열, 연결리스트를 사용할 수 있습니다. 

그중에서 저는 헤더와 트레일러 노드가 있는 이중연결리스트를 구현해보도록 하겠습니다. 

 

연결리스트를 이용한 구현->이중연결리스트

 

마지막으로 배열과 연결리스트의 성능을 비교하고 끝내도록 하겠습니다~

성능요약

작업 배열 연결리스트
size, isEmpty 1 1
get, set 1 n
add, remove n n
addFirst, removeFirst n 1
addLast, removeLast 1 1

 

'Computer Science/자료구조' 카테고리의 다른 글
  • 6. 집합 ADT
  • 5. 리스트 확장-그룹과 공유
  • 3. 기초 데이터 구조
  • 2. 재귀
SpaceCowboy
SpaceCowboy
공부한거 기록하는 블로그입니다!!
SpaceCowboy
공부한거 기록하는 블로그
SpaceCowboy
전체
오늘
어제
  • 분류 전체보기
    • 프로그래밍 언어
      • C Programming
      • JavaScript
    • Computer Science
      • 자료구조
      • 알고리즘
      • 객체지향
    • 프레임워크
      • Nest.js
      • TypeORM
    • Web Programming
    • 블록체인
      • 기초
    • 데브옵스
      • Git
      • Docker

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • TypeORM
  • nestjs
  • 자료구조필기
  • 자바스크립트
  • JS
  • 자바스크립트필기
  • typeormseeding
  • 복습
  • typeorm0.3
  • 이중연결리스트
  • 자료구조
  • typeorm3.0
  • CSS
  • 논리삭제
  • customrepository
  • 자바스크립트 필기
  • softDelete
  • 재귀
  • HTML
  • 자바스크립트챌린지

최근 댓글

최근 글

hELLO · Designed By 정상우.
SpaceCowboy
4. 리스트 ADT
상단으로

티스토리툴바

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.