typedef int element;
typedef struct {
int list[MAX_LIST_SIZE]; //define array
int length; // the number of items
}ArrayListType;
void init (ArrayListType *L) {
L->length = 0;
}
int is_empty(ArrayListType *L) {
return L->length == 0;
}
int is_full(ArrayListType *L) {
return L->length == MAX_LIST_SIZE;
}
// 1) 배열이 포화상태인지 확인.(Is saturated?) -> insertion 위치 범위체크
// 2) 삽입 위치 뒤에 items를 한칸씩 뒤로 옮긴다.
void add(ArrayListType *L, int position, element item){
if (!is_full(L) && (position >=0) &&(position <= L->length)) {
int i;
for (i=(L->length-1); i>=position;i--)
L->list[i+1] = L->list[i]; //한칸씩 뒤로 미룬다. 공간만들어주기
L->list[position] = item;
L->length++;
}
}
// 1) 적절한 index인지 확인 (Confirm whether the index is appropriate)
// 2) 삭제위치 뒤의 items를 한칸씩 앞으로 땡긴다.
element delete(ArrayListType *L, int position){
int i;
element item;
if (position<0 || position >= L->length) error("Position error");
item = L->list[position];
for (int i = position; i<L->length;i++)
L->list[i] = L->list[i+1];
L->length--;
return item;
}
#2 Linked List
Node들의 리스트. physical order != logical order이다. (메모리에 저장된 주소순서 != 실제 리스트의 논리 주소 순서) ` Node = [ data | link ] `: data(element), link(address of another node) Head pointer : linked list의 첫번째 node를 가리키는 *포인터 ( address of first node),
Dynamic Memory Allocating(동적 메모리 할당)을 통해 노드를 생성한다.
`Pros` + 삽입/삭제(Insertion/ Deletion) 이 효율적임.(메모리 측면에서) + 크기 제한이 없다. + consecutive한 메모리 공간이 필요 없다. *consecutive = 연이은 `Cons` - 구현이 복잡하다. - 에러가 잘 난다.
Simple linked list : 단방향, 마지막 노드의 링크가 NULL
Circular linked list : 단방향, 마지막 노드의 링크가 first node
Doubly linked list : 양방향, Node = [ llink | data | rlink ] 로 구성됨. first_node의 llink = null, last_node의 rlink = null
#2.1 Simple linked list
기본 defination
typedef int element;
typedef struct ListNode {
element data;
struct ListNode *link;
} ListNode;
`**phead`는 list의 head pointer를 가리키는 pointer pointer -> head pointer(address of first node), 즉 address of address (주소를 가리키는 주소!)
void insert_first(ListNode **phead, ListNode *new_node) {
if (*phead == NULL) {
// if the list is blank
new_node->link = NULL;
*phead = new_node;
} else {
new_node->link = NULL;
*phead = new_node;
}
}
4. Insertion in the end of the list
void insert_last(ListNode **phead, ListNode *new_node) {
if (*phead == NULL) {
// if the list is blank
new_node->link = NULL;
*phead = new_node;
} else {
new_node->link = NULL;
ListNode *last = *phead;
while (last->link != NULL) // 리스트의 마지막 노드의 주소를 last에 담는다. 결과 last->link == NULL인 상태.
last = last->link;
last->link = new_node;
}
}
p21의 Questions.
Can we implement a single, unified function for both insertion and deletion, instead of using separate functions (p24-p30) that serve similar roles? → yes! (See the code below.)
If so, how would this unified function be designed and implemented? → first, we should distinguish between insertion or deletion by using a flag (0 for insertion and 1 for deletion) second, we can implement by using if-else conditional statements.
What are the potential pros and cons of using one unified function compared to multiple specialized functions `Pros` Improves reusability and reduces redundancy `Cons` Decreases readability and may require unnecessary parameters. It can also violate the Single Responsibility Principle (SRP) in the SOLID design principles.
void insertion_deletion(int flag, ListNode **phead, ListNode *before_node, ListNode* node) {
if (flag == 0)
{
if (*phead == NULL) {// case1 if the list is blank
node->link = NULL;
*phead = node;
}else if (before_node == NULL) { // case2 first에 넣기
node->link = *phead;
*phead = node;
} else {//case3&4, middle에 or end case4 end에 삽입
node->link = before_node->link; // NULL이어도 그대로 받아가면 된다.
before_node->link = node;
}
}
else if (flag == 1)
{
if (*phead == NULL) error("The list is blank");
else {
if (before_node == NULL) {
*phead = (*phead)->link; // *phead = removed였으니까 그 다음거로 옮겨준다.
}else {
before_node->link = node->link;
}
free(node);
}
}
else
error("invalid range value. must be 0 or 1 [ insertion : 0 | deletion : 1 ]");
}
하나의 node가 두 개의 link를 가진다. preceding node subsequent node의 address를 가지는 link! [preceding node]<- [ llink | data | rlink] -> [subsequent node] 기존의 simple linked list에서는.... 1) preceding node 찾기 어려웠음. 2) 삽입/삭제 시 같이 parameter로 주어야 했음. →해결! `Pros` link가 양방향을 가리키므로, 두 방향으로 탐색 가능 `Cons` 공간을 많이 차지하고, 코드가 복잡함.
`head node(더미 노드)`를 사용하면, 별도의 head pointer가 필요 없다!
Head node : 실제데이터X, 삽입/삭제를 쉽게하기 위해 만듦. head pointer와는 구분된다.!!!! 빈 리스트일 때는 only headnode만 존재한다.
이해를 돕기위해 소괄호()를 추가함. 삭제해도 무방하다. 1 2 3 4 중 1 2 는 순서 바뀌어도 괜찮음. 다만 (1,2)->3->4 는 유지. ▼ Implementation of Doubly Linked List insertion
Can the existing functions (p41-p42) for insertion (or deletion) in a doubly linked list be used to insert (or delete) at the beginning or at the end of the list? → Yes, they can be used, as long as the correct before node is provided. If only the data value of before is known and not its exact address, the corresponding node must be found through a search before calling the function.
If not, how can you modify these functions so that they also handle insertion and deletion at the beginning or the end of the list? - Beginning insertion → head_node 뒤에 삽입. `dinsert_node(head_node, new_node)` - End insertion → tail 노드 뒤에 삽입 `dinsert_node(tail, new_node)` - Beginning deletion → `head_node->rlink`를 `removed`로 주면 가능 `dremove_node(head_node,first_node)` -End deletion → tail 노드를 찾아서 `dremove_node(head_node, tail)`
#3. Application : Polynomial
x에 대한 다항식 A를 linked list로 나타낼 수 있다.
typedef struct ListNode {
int coef;
int expon;
struct ListNode *link;
}ListNode;
