연결리스트(Linked List) - C언어

연결리스트(Linked List) - C언어

▶ 배열 기반 리스트의 특징

- 특정 위치 원소에 즉시 접근 가능

- 데이터가 들어갈 공간을 미리 할당해야 함

- 원하는 위치로의 삽입, 삭제가 비효율적 (매 번 모든 값을 이동시켜 주어야 함)

▶ 배열 기반 리스트 소스코드 (C언어)

#define CRT_SECURE_NO_WARNINGS #include #include #include #define INF 10000 // 충분히 큰 수 int arr[INF]; // 충분히 큰 배열 생성 int count = 0; // 카운트 변수 초기화 // 배열 맨 뒤에 요소 추가 void addback(int data){ arr[count] = data; count++; } // 배열 맨 앞에 요소 추가 void addfirst(int data){ for(int i = count ; i >= 1 ; i--){ arr[i] = arr[i-1]; // 한 칸씩 밀기 } arr[0] = data; count++; } // 특정 인덱스 요소 추가 void addAt(int index, int data){ for(int i = count;i >= index ;i--){ arr[i+1] = arr[i]; } arr[index] = data; count++; } // 특정 인덱스 요소 삭제 void removeAt(int index){ for(int i = index; i < count - 1; i++){ arr[i] = arr[i + 1]; } count--; } // 배열 출력 void show(void){ for(int i = 0; i < count; i++){ printf("%d ", arr[i]); } } int main(void) { addback(3); addback(4); addback(5); addfirst(2); addfirst(1); addAt(3, 7); show(); system("read"); return 0; }

출력값 -> 1 2 3 7 4 5

▶ 연결 리스트의 특징

- 구조체와 포인터를 함께 사용하여 구현

- 리스트 중간 지점에 노드 추가 및 삭제가 가능해야 함

- 필요할 때마다 공간을 할당받음

▷ 단일 연결 리스트

<단일 연결 리스트>

from http://itscool.tistory.com/19 by ccl(A) rewrite - 2021-09-01 00:00:32