티스토리 뷰
ArrayList(순차 리스트) - 배열 기반 구현 리스트
LinkedList(연결 리스트) - 메모리의 동적할당 기반 구현 리스트
구현 방법 기준으로 한 구분으로 두 리스트의 ADT는 동일
리스트 자료구조는 데이터를 나란히 저장하고, 중복 데이터의 저장을 허용한다.
배열리스트의 장점과 단점
장점 - index값만 기준으로 해서 데이터 참조가 쉽다
단점 - 배열길이가 초기에 결정되어 변경이 불가능하다. 삭제과정에서 데이터 이동 빈번히 일어난다.
//정수만 저장되어 있는 배열리스트
type def LData의 사용 이유

1. int형이라고해서 어느 CPU에서나 4바이트가 아니다.
16비트와 8비트에서의 CPU에선 int가 2바이트, 1바이트로 다르기 때문에
여러 시스템 환경(CPU가 다른)에서도 동일하게 사용가능하다
2. 자주쓰는 데이터를 편하고 쉽게 인식하기 위해서 사용한다.(아래 리스트에서도 정수를 뜻하는 LData로 명시하였다. 물론 LData를 따로 선언하지않고그냥 int로 모두 대체해도 상관없음. )3. Swift의 typealias와 동일한 기능으로 코드의 가독성를 높이는데도 사용된다.
배열리스트 구현하기(교재와는 조금 다르게 구현했지만 기능은 동일함)
#include<stdio.h>
#pragma warning(disable: 4996)
//Bool타입 메크로 정의
#define TRUE 1
#define FALSE 0
#define LIST_LEN 100 //배열길이
typedef int LData; //자료 저장할 대상의 자료형
typedef struct ArrayList{
LData arr[LIST_LEN];
int numOfData; //데이터 수
int curPosition; //데이터 참조 위치
}ArrayList;
//
typedef ArrayList List;
//
//함수
void ListInit(List * plist); //리스트의 주소값을 파라미터로 받아 리스트 생성
void LInsert(List * plist, LData data); //리스트에 데이터 저장
int LFirst(List * plist, LData * pdata); //첫번째 데이터 참조하여 변수 pdata에 저장
int LNext(List * plist, LData * pdata); //LFirst이후의 데이터 참조
LData LRemove(List * plist); //참조한 데이터 삭제
int LCount(List * plist); // 저장 데이터 수 반환
void ListInit(List * plist){
plist -> numOfData = 0;
plist -> curPosition = -1; // 그 어떤index도 참조하지 않고 있음을 -1로 초기화
}
void LInsert(List * plist, LData data){
if(plist -> numOfData >= LIST_LEN)
{
printf("배열이 꽉 차서 데이터 추가 불가\n");
}
plist -> arr[plist -> numOfData] = data;
(plist -> numOfData)++;
}
int LFirst(List * plist, LData * pdata){
//빈 배열이 아닌지부터 확인(데이터가 없을수도 있다)
if(plist -> numOfData == 0) return FALSE; //실패임을 알리는 FALSE
plist -> curPosition = 0; //참조 위치 curposition을 배열의 첫번째 index인 0으로 초기화
*pdata = plist -> arr[plist -> curPosition]; //첫번째 데이터를 변수 pdata에 저장
return TRUE; //참조 위치 초기화 및 첫번째 데이터 저장에 성공했음을 TRUE로 반환
}
int LNext(List * plist, LData * pdata){
(plist -> curPosition)++; //curPosition 다음위치(한칸뒤로) 이동
//그 다음 참조 위치 curPosition에 저장된 데이터가 없을수도 있음
if(plist -> curPosition > plist -> numOfData - 1) return FALSE; //실패를 알리는 FALSE
*pdata = plist -> arr[plist -> curPosition]; //next데이터를 변수 pdata에 저장
return TRUE; //next데이터 저장에 성공을 TRUE로 반환
}
LData LRemove(List * plist){
LData removeData; //삭제할 데이터 임시 저장 removeData
removeData = plist->arr[plist ->curPosition];
//삭제할 데이터 미리 저장
for(int i = plist -> curPosition; i < plist ->numOfData-1;i++) //삭제데이터 기준으로 마지막데이터까지로 범위 지정
{
plist -> arr[i] = plist -> arr[i+1]; //삭제 데이터 기준 1칸씩 땡겨오기. 마지막의 arr[numOfData -1]까지
}
(plist -> numOfData)--; //삭제햇으니 데이터 수 감소시키기
(plist -> curPosition)--; //참조위치가 1칸뒤로 밀려낫기에 다시 땡겨오기
return removeData;
}
int LCount(List * plist)
{
return plist->numOfData;
}
int main()
{
//ArrayList의 생성 및 초기화
List list;
int data;
ListInit(&list);
//5개의 데이터 저장
LInsert(&list, 11); LInsert(&list, 11);
LInsert(&list, 22); LInsert(&list, 22);
LInsert(&list, 33);
//저장 데이터 전체 출력
printf("현재 데이터의 수: %d \n", LCount(&list));
if(LFirst(&list, &data)) // 첫번째 데이터 조회
{
printf("%d ", data);
while(LNext(&list, &data)) // 두번째 이후 데이터 조회
{
printf("%d ", data);
}
}
//숫자 22 탐색하여 모두 삭제
if(LFirst(&list, &data))
{
if(data == 22)
LRemove(&list);
while(LNext(&list, &data))
{
if(data == 22)
LRemove(&list);
}
}
//삭제후 남은 데이터 수와 전체 데이터 출력
printf("현재 데이터의 수: %d \n", LCount(&list));
if(LFirst(&list, &data))
{
printf("%d ", data);
while(LNext(&list, &data))
printf("%d ", data);
}
printf("\n\n");
return 0;
}
반응형
'TIL [자료구조&알고리즘]' 카테고리의 다른 글
[C] 이중 원형 연결 리스트(DoublyCircularLinkedList) (0) | 2023.03.14 |
---|---|
원형 연결 리스트(CircleLinkedList) (0) | 2023.03.06 |
4. 더미노드 있는 연결 리스트(DummyLinkedList) (0) | 2023.03.05 |
3. 단일 연결 리스트(SingleLinkedList) (0) | 2023.03.05 |
1. 알고리즘 성능 분석 수단(Time Complexity, Big O) (0) | 2023.02.28 |