Search
Duplicate
🪄

[자료구조] 리스트

간단소개
자료구조 스터디 1주차의 내용을 복습 차 정리해보았습니다~ 리스트의 2가지 방식을 소개합니다!
팔만코딩경 컨트리뷰터
ContributorNotionAccount
주제 / 분류
자료구조
Scrap
태그
자료구조
9 more properties

추상 자료형(Abstract Data Type)

추상적으로 자료형을 정의
객체와 함수들이 존재
배열 리스트의 추상 자료형 예시
자료구조는 추상 자료형을 프로그래밍 언어로 구현한 것이라고 볼 수 있다!

리스트

항목들을 차례로 저장하는 방법 (버킷 리스트 등)

1) 배열 리스트

배열을 기반으로 구현된 리스트

2) 연결 리스트

노드의 동적 할당을 기반으로 구현된 리스트
노드(Node)
Search
배열리스트
연결리스트
구현이 간단한 편, 인덱스로 임의의 항목에 바로 접근 가능
리스트의 크기가 제한되지 않음, 삽입과 삭제가 유연함
리스트의 크기가 고정됨, 삽입과 삭제 시 기존의 데이터들을 이동시켜야 함
구현이 복잡한 편, 임의의 항목을 추출할 때 시간이 많이 걸림

연결 리스트의 종류

1) 단방향 연결 리스트

2) 원형 연결 리스트

3) 이중 연결 리스트

구현한 리스트 구조

// 단방향 연결 리스트 헤더 일부 typedef struct ListNodeType { int data; struct ListNodeType* next; } ListNode; typedef struct LinkedListType { int currentElementCount; ListNode *headerNode; } LinkedList;
C
복사
LinkedList라는 구조체에 연결 리스트의 정보(현재 노드 개수, 헤더 노드 포인터)를 저장
헤더 노드(더미노드) : 리스트에서 실질적인 데이터를 가지는 첫번째 노드를 가리키도록 하는 노드
노드는 데이터 필드와 링크 필드로 나뉘는데 데이터 필드에 저장하고 싶은 데이터를 저장하고, 링크 필드에는 다른 노드를 가리키는 포인터가 저장된다
이중 연결 리스트는 2개의 링크 필드를 갖는다