[Data Structures - 자료구조 이해] Arrays, Linked lists

데이터를 저장하는 4가지 방법

• Arrays
• Linked lists
• Hash tables
• Tries

이 외에도 여러가지 변형이 있다.

Trees와 Heaps는 Tries와 유사함

Stacks와 Queues는 Arrays 또는 Linked lists와 유사함

▼ Hash Tables 와 Tries에 대한 발행글

2023.06.08 - [Programming] - [Data Structures - 자료구조 이해] Hash Tables, Tries

 

---

Arrays

• 삽입 Bad  /  삭제 Bad (크기가 고정되어있기 때문에 힘들다)
• 검색 좋음  /  정렬 쉬움
• 상대적으로 작은크기
• 크기가 고정되어 있다.

 

---

Linked list

• 삽입 쉬움  /  삭제 쉬움 
• 검색 Bad  /  정렬 Bad 
• 상대적으로 작은 크기 ( Arrays만큼 작지는 않다)

검색은 선형검색(linear search) 방식임

정렬하려면 처음에 생성, 값 삽입할 때부터 정렬해야 함 -> 장점이던 빠른 삽입이 불가능

 

---

생성

// Singly-Linked lists
typedef struct sllist
{
	VALUE val;
	struct sllist *next; // 자기참조
}
sllnode;


sllnode *create(VALUE val); // linked lists 생성
sllnode *new = create(6); // 새 sllnode를 위한 공간 동적할당

sllist는 임시이름이고, struct sllist *next; 에서 자기참조를 할 때 사용했다.

 

linked list를 생성하는 단계

새로운 sllnode를 위한 공간 동적할당 → 메모리 부족 여부 확인(NULL체크) → 해당 sllnode의 val 초기화 → 해당 sllnode의 next 초기화 → 새로 만든 sllnode를 향한 포인터( = *new) 반환 

 

---

삽입

sllnode *insert(sllnode *head, VALUE val);

list = insert(list, 12);

head는 list의 첫번째 node를 가리키는 포인터이다.

목록을 순서대로 정렬하는 것은 linked list에선 중요하지 않다.

 

linked list를 삽입하는 단계

새로운 sllnode를 위한 공간 동적할당 → 메모리 부족 여부 확인(NULL체크) → linked list의 시작 부분에 node를 삽입 → 새로운 head를 향한 포인터 반환 

주의) 새로운 node를 삽입할때 새로운 node의 next가 기존 head와 같도록 한다.
(같은 곳을 바라보도록 한다 = 기존 list와 새로운 node 연결한다) 그 후에 list의 head값을 변경한다.

 

---

삭제

void destroy(sllnode *head);

destroy(list);

head는 list의 첫번째 node를 가리키는 포인터이다.

목록 끝에 있는 node의 next는 NULL이다.

 

linked list를 전체삭제하는 단계

NULL이면 중지 → 나머지 list 삭제(재귀) → 현재 node의 메모리 해제(free)

참고) 단일 삭제는 두 개의 포인터를 이용해서 한 node를 건너뛰고, 연결시킨 후 삭제해야한다. = 복잡하다
 Double linked list를 이용해서 단일 삭제한다.

 

---

검색

bool find(sllnode *head, VALUE val);

bool exists = find(list, 6);

head는 list의 첫번째 node를 가리키는 포인터이다.

val은 찾는 값이다.

목록 끝에 있는 node의 next는 NULL이다.

 

linked list를 검색하는 단계

해당 linked list의 head를 가리키는 또 다른 포인터 생성

 → 만약 해당 node의 val이 찾는 값이라면 성공

 → 그렇지 않다면 포인터를 next 포인터의 값으로 설정하고 이동

 ...

→ 목록의 끝에 도달한 경우 실패

 

---

Singly-Linked list와 Doubly-Linked list

Linked list는 데이터를 수집하고 구성하는 능력이 뛰어나다.

하지만, Singly-Linked list는 한 방향으로만 움직일 수 있다. 따라서 Singly-Linked list에서는 단일삭제가 어려웠다.

하지만, Doubly-Linked list는 struct정의에 포인터 하나만 추가하면, list를 앞 뒤로 이동 할 수 있다!

 

생성

// Doubly-Linked lists
typedef struct dllist
{
	VALUE val;
	struct dllist *prev; // 자기참조
	struct dllist *next; // 자기참조
}
dllnode;


dllnode *create(VALUE val); // linked lists 생성
dllnode *new = create(6); // 새 dllnode를 위한 공간 동적할당

dllist는 임시이름이고, struct dllist *pext, struct dllist *next 에서 자기참조를 할 때 사용했다.

 

linked list를 생성하는 단계 (동일)

새로운 dllnode를 위한 공간 동적할당 → 메모리 부족 여부 확인(NULL체크) → 해당 dllnode의 val 초기화 → 해당 dllnode의 next 초기화 → 새로 만든 dllnode를 향한 포인터( = *new) 반환 

 

---

삽입

dllnode *insert(dllnode *head, VALUE val);

list = insert(list, 12);

head는 list의 첫번째 node를 가리키는 포인터이다.

 

linked list를 삽입하는 단계

새로운 dllnode를 위한 공간 동적할당 → 메모리 부족 여부 확인(NULL체크) → linked list의 시작 부분에 node를 삽입 → list의 기존 head가 가리키는 dllnode의 prev pointer를 수정한다 (prev가 새로운 node의 val을 가리킨다) → 새로운 head를 향한 포인터 반환 

 

---

삭제

void delete(dllnode *target);

destroy(x);

target은 삭제할 node를 가리키는 포인터이다.

목록 끝에 있는 node의 next는 NULL이다.

 

linked list를 단일삭제하는 단계

NULL이면 중지 → target node의 앞 뒤 node의 포인터(prev, next)를 수정한다 (잘 이어질 수 있게 수정한다) → target 메모리 해제(free)