[자료구조] 배열을 이용한 리스트 구현

2023. 12. 24. 15:51·Data Structure/자료구조

배열을 이용한 리스트 구현 - 순차 리스트, 연결 리스트


  • 순차 리스트 : 배열을 기반으로 구현된 리스트

  • 연결 리스트 : 메리의 동적 할당을 기반으로 구현된 리스트

    --> 두 리스트는 ADT(기능)는 동일, 구현방법만 다름.

  • 리스트의 특징

    • 저장형태 : 데이터를 나란히 저장한다. (어느 방향으로 저장하든 상관 없다.)

    • 저장 특성 : 중복이 되는 데이터의 저장을 허용.

      --> 배열과 연결을 기반으로 함.

  • 배열 기반 리스트의 단점

    • 배열의 길이가 초기에 결정되어야 함. 변경이 불가능

    • 삭제의 과정에서 데이터의 이동(복사)가 매우 빈번히 일어남.

  • 배열 기반 리스트의 장점

    • 데이터의 참조가 쉽다. 인덱스 값 기준으로 어디든 한 번에 참조 가능.

리스트 자료구조의 ADT(기능)

  • 리스트의 초기화
void ListInit(List *plist);
- 초기화할 리스트의 주소 값을 인자로 전달
- 리스트 생성 후 제일 먼저 호출되어야 하는 함수
  • 데이터 저장
void LInsert(List *plist, LData data);
- 리스트에 데이터를 저장하고, 매개변수 data에 전달된 값을 전달.
  • 저장된 데이터의 탐색 및 탐색 초기화 : 조회를 처음부터 다시 시작하겠다.
int LFirst(List *plist, LData *pdata);
- 첫번째 데이터가 pdata가 가리키는 메모리에 저장됨.
- 데이터의 참조를 위한 초기화가 진행됨
- 참조 성공시 True, 실패시 False 반환
  • 다음 데이터의 참조를 목적으로 호출
int LNext(List *plist, LData *pdata);
- 참조된 데이터의 다음 데이터가 pdata가 가리키는 메모리에 저장됨
- 순차적인 참조를 위해서 반복 호출이 가능
- 참조를 새로 시작하려면 먼저 LFirst 함수 호출
- 참조 성공시 True, 실패시 False 반환
  • 바로 이전에 참조(반환)이 이뤄진 데이터의 삭제
LData LRemove(List *plist);
- LFirst 또는 LNext 함수의 마지막 반환 데이터를 삭제
- 삭제된 데이터 반환
- 마지막 반환 데이터를 삭제하므로 연이은 반복 호출 허용 X
  • 현재 저장되어 있는 데이터의 수를 반환
int LCount(List *plist);
- 리스트에 저장되어 있는 데이터의 수를 반환
  • LFirst와 LNext가 따로 있는 이유

    • LFirst는 배열의 처음부터 확인할 때 쓰는 거고, LNext는 1번, 2번... 순차적으로 확인할 때 사용하는데, 대부분 라이브러리가 이런 구조를 활용함
  • ex) LData에 Point 구조체가 들어가는 경우.

    • ArrayList.h 파일과 메인 함수가 포함된 c파일만 수정하면 됨.
    • ArrayList.c 함수 코드를 수정할 필요가 없다.

참조) 윤성우의 열혈 자료구조 (윤성우, 오렌지미디어)

'Data Structure > 자료구조' 카테고리의 다른 글

[자료구조] 스택(Stack)  (0) 2023.12.31
[자료구조] 배열의 응용 : 희소행렬  (0) 2023.12.26
[자료구조] 배열의 응용 : 다항식  (0) 2023.12.26
[자료구조] 순차리스트  (0) 2023.12.24
[자료구조] 추상 자료형(Abstract Data Type)  (0) 2023.12.24
'Data Structure/자료구조' 카테고리의 다른 글
  • [자료구조] 배열의 응용 : 희소행렬
  • [자료구조] 배열의 응용 : 다항식
  • [자료구조] 순차리스트
  • [자료구조] 추상 자료형(Abstract Data Type)
lumana
lumana
배움을 나누는 공간 https://github.com/bebeis
  • lumana
    Brute force Study
    lumana
  • 전체
    오늘
    어제
    • 분류 전체보기 N
      • Project&&Service
        • Performance
        • TroubleShooting
        • Refactoring
      • Spring N
        • MVC
        • DB
        • 핵심 원리
        • JPA N
      • WEB
        • HTML
        • CSS
        • HTTP
        • Application
      • Computer Science
        • Network
        • Database
        • OS
        • 시스템 프로그래밍
        • 컴퓨터구조
      • Algorithm
        • Divide&Conquer
        • Sort
        • Greedy
        • DP
        • Backtracking
        • NP-Complete
        • Graph
      • Data Structure
        • 자료구조
        • C++ STL
        • Java Collection
      • 소프트웨어 공학
        • 시험 공부 정리
        • Theorem
      • Programming Language N
        • Python
        • Java N
        • C
        • C++
        • Rust
        • Theory
      • Unix_Linux
        • Common
      • React
      • PS
        • BOJ
        • Tip
        • 프로그래머스
        • CodeForce
      • Book Review
        • Clean Code
      • Math
        • Linear Algebra
      • AI
        • DL
        • ML
        • DA
        • Concepts
      • 우아한테크코스
        • 프리코스
      • Project Review
      • LegacyPosts
      • Android
      • Apple
        • Mac
        • IPhone
        • IPad
      • 모니터
      • Diary
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

  • 공지사항

  • 인기 글

  • 태그

  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
lumana
[자료구조] 배열을 이용한 리스트 구현
상단으로

티스토리툴바