List

Linked list

저장되어 있는 위치 무관하게 저장되어 있고, 다음 변수를 순서대로 가리키고 있는 것

-> struct/class 같은 자료형으로 변수 data와 다음꺼 가리키는 pointer을 갖도록 함

- 첫번째에는 값 X. 그냥 헤더로 쓰인다

- 실제로 어디 저장되어 있는지는 무관 ! 인접할 필요 없음

- 각 linked list는 일련의 strucrture로 구성되어 있다 (인접필요는 xx) 

  -> element & pointer를 가짐

- 마지막 친구는 다음 포인터로 NULL를 갖게 됨

---

코드들

* ElementType = 담을 데이터의 자료형

* Position = 해당 Node의 다음꺼 가리키는 포인터 인 듯?

( List, Position 둘다 노드 가리키는 포인터 )

예이 ~~!!~~

Linked list implementation (위치 알아내기). 찾기 ~~ 없으면 null~~

// position 찾기. 즉 해당 x 변수가 담겨있는 Node(포인터)찾기 !
Positioin Find(ElementType x, List L) // 리스트 = 노드 포인터. 여기선 헤드 노드가 주어지겠지여
{
    Position P = L->next; //next부터 시작 -> 해당 변수를 그대로 검사함 (다음꺼/전꺼 검사하는게 아님)
    while (P!=NULL &&P->Element!=x) // 해당 변수에 x가 담겨있거나, null이야(걍 없는 거. 이미 초과한거) -> 이제 나와서 그거 리턴됨
    	P=P->Next;
    return P; // 그냥 P 바로 리턴 !!
}

null이 아니고 데이터도 아닐때만 다음노드로 이용 !! (while loop의 의미^^)

 

node 선언

struct Node 
{
    ElementType element;
    Position Next;
}

비엇는지

int isEmpty(List L){
    return L->Next==NULL; // 헤드가주어질텐데 그거 다음값이 바로 null = 비었다 ! 그리고 이렇게 리턴문에 == 으로 한번에가능
}

마지막인지

int isLast(Position P){
    return P->Next==NULL;
    // 해당 주어진 노드포인터 다음꺼가 없으면 last이므로 !
}

이전 노드 찾기

Position FindPrevious(ElementType X, List L){
    Position P=List; //list->next 하면 안됨!!!
    while(P->Next!=NULL && P->Next->Element!=X) // 딱 null이 되거나 x가 될 때 while멈춤! 그리고 그값을 리턴하게 됨 !! !=인거 꼭 알기
    	P=P->Next;
    return P;
}

그냥 해당 노드 찾을때는 해당 노드가 null인지, x 갖고 있는지 보지만,

다음 노드가 값 갖는거 찾을 때는 다음 노드가 null인지, 다음 노드가 x갖고 있는지 본다

그리고 둘중 하나라도 맞으면 해당 노드를 리턴한다 !

 

삭제 연산

void Delete (ElementType X, List L){
    Position P, TmpCell;
    P=FindPrevious(X);
    
    // 해당 노드가 없다->previous node 찾은 애의 다음이 NULL이겟죠? -> 마지막 노드겟져?
    if(!isLast(P,L)){
        TmpCell=P->Next; //이거 없어질 꺼니까 미리 담아놓음 !!
        P->Next=Tmp->Next; // 마지막 노드가 삭제되더라도 ㄱㅊ음 P->Next에 NULL 들어가고 굳~
        free(TmpCell);
    }
}

!! free(tmpCell) 이고

해당 노드가 마지막이 아닐때만 해야하고 !

tmpCell=p->next 먼저 담아두기

!! 항상 가운데 낑기는애를 tmp에 담아두기 !!

그리고 P->Next=tmp->Next 하기 ~~

 

insert 연산

void Insert (ElementType X, List L, Position P){ // 해당 포지션 다음에 넣는 것
    Position TmpCell=malloc(sizeof(struct Node)); // malloc은 자료형크기받아서 그 주소할당해서 그 주소를 반환함 ! 그래서 무조건 포인터 써야댐
    if(TmpCell==NULL)
    	FatalError("Out of space !!")
    
    TmpCell->Element=X; // 내용 넣기도 꼭 해주기 ~
    TmpCell->Next=P->Next; // 뒤에꺼 먼저 ~ 
    P->Next=TmpCell; 
}

 

-> Doubly linked list

Node

struct Node{
    ElementType Element;
    Position Next;
    Position Prev;
}

insert

void Insert (ElementType X, List L, Position P){
    Position tmp=malloc(sizeof(struct Node));
    //null -> fatal error (할당 실패이므로)
    tmp->Element=X;
    
    tmp->next=P->next; // tmp 정보 먼저 설정
    tmp->next->prev=tmp;
    p->next=tmp;
    tmp->prev=p; // prev의 앞,뒤 정보 모두 설정해줘야함 ~

delete

void Delete (ElementType X, List L)
{
    Position tmp=Find(X);
    tmp->prev->next=tmp->next; // 전꺼부터 !
    tmp->next->prev=tmp->prev;
    free(tmp); //이거안하뉘 ..??
}

// tmp의 next, prev는 무관 ! 안바뀜 !! (걍조용히 free되면서 삭제됨)

걍전꺼부터하좌 ..^^ pdf가 그랫어..

-> Circularly linked list

= 맨 처음과 끝이 연결된 것 !!

---

Polynomial with linked list !

전에는 array 형식으로 담았다면, 이제는 각항을 node로 정의한 후 linked list 방식을 쓴다 !

(Coeff = 계수)

(Order/exponent = 지수)

 

attach (맨 뒤에 해당 항 붙임)

* 이때 이전 노드를 찾아서 안하고 그냥 해당 노드와 다음노드를 입력받은 값으로 바꿔줌

이걸로 계속 추가하면 마지막 원소가 결국 똑같은거 하나 더잇게 됨 -> add 연산시 마지막에 지워줌 (대체왜)

void attach (float coeff, int expon, polyPointer* ptr){ // 이때 ptr은 포인터의 포인터 !!!
    //주어진 포인터 자리에 해당 계수,지수를 갖는 항을 붙인다 -> 맨 끝에 붙인다 !
    polyPointer tmp;
    MALLOC (tmp, sizeof(*tmp)); //걍 tmp에 malloc햇다고 생각하자
    
    tmp->coef=coeff;
    tmp->expo=expon;
    
    *ptr->link=tmp;
    *ptr=tmp;
}

 

add 덧셈

- 두 식을 가리키는 포인터 ai, bi 만듦

- 지수가 같으면 연산해서 식에 적어주고 두 포인터 다를 작은쪽으로 옮겨준다

- 다르면 더 큰쪽을 식에 적어주고 큰거를 왼쪽으로 하나 옮긴다

- 한쪽을 다하면 남은 애를 그 식에 고대로 더해준다 (순서대로 연결)

poly_pointer padd(poly_pointer a, poly_pointer b){
    poly_pointer c, rear, tmp;
    int sum;
    MALLOC(rear, sizeof(*rear));
    c=rear; //걍 동적할당 인듯?
    
    while(a&&b){//둘다 존재할 때. null이 아닐 때 !!)
        switch(COMPARE(a->expon, b->expon)){
            case -1: // b가 더 클 때
                attach(b->coef, b->expon, &rear);
                b=b->link;
                break;
            case 0: //같을 때
                attach(a->coeff + b->coeff, b->expon, &rear);
                a=a->link;
                b=b->link;
                break;
            case 1: //a가 더 클 때
                attach (a->coef, a->expon. &rear);
                a=a->link;
                break;
            }
     }
     // 나머지를 싹 다 붙인다 분명 하나는 다 썻을거임 ! a/b가 null이 아닐 때 까지만 돌아감!
     for (;a;a=a->link) attach(a->coef,a->expon,&rear);
     for (;b;b=b->link) attach(b->coef,b->expon,&rear);
     rear->link=NULL;
     // extra initial node를 삭제한다
     temp=c;
     c=c->link;
     free(temp);
     return c;
 }

 

- 이 덧셈 연산의 복잡도는

 

erasing (항 지우기)

void erase(polyPointer *ptr){ // 전부 다 지우는 거
    // 임시를 삭제한다 !!!
    polyPointer tmp;
    while(*ptr){ //존재할 때까지 
        tmp=*ptr;
        *ptr=(*ptr)->link;
        free(temp);
    }
}

ptr로 다음 노드들 계속 가리키게 하고, temp를 삭제한다 !

 

Circular list representation of poly

= 맨뒤에가 맨 앞에를 가리키는 것

코드

* avail은 내가밧을때 사용가능한 빈 노드(들. 연결되어잇는)인듯

♡ 노드하나 할당받는거

node* getNode(void){

    if(avail){ //사용가능 노드 잇으면

         node=avail; avail=avail->link;

    }

   else node=malloc함 ! 

   return nodel

}

 

♡ avail 리스트에 노드 하나 반환하는거

void retNode(node* node){

    node->link=avail;

    avail=node;

}

 

♡ circular list 없애는거 - 루프 X ! 상수번 (4번의 연산 함)

void cerase(node* ptr){

    node* temp;

    if (*ptr){

        temp=(*ptr)->link;

        (*ptr)->link=avail;

        avail=temp;

        (*ptr)=NULL;

    }

}

ptr의 다음꺼를 temp에 넣어두고

ptr의 다음을 이제 쓸 수 있게 avail을 넣어둔다

avail=temp (흠) avail에 이제 안쓰는 ptr->link를 넣어주고

ptr=NULL!!

 

---

Additional list operations

typedef struct listNode *listPointer;
typedef struct listNode{
    char data;
    listPointer link;
}

1. invert single linked lists

: linked list 거꾸로 만드는거 !!

( trail, middle은 연산 위해 새로 만든 포인터임~)

trail=middle ; 이따 미들에 담을 현재 lead 노드의 직전 노드를 trail에 담아줌

middle=lead;

lead=lead->link;

middle->link=trail;

 

2. concatenate two linked lists

: 두 링크드리스트를 잇는다

-> ptr1의 끝을 찾아서 그거의 링크를 ptr 2로 하면 됨!

3. operations for circularly Linked List

-> 맨 앞에 원소 넣을때 뒤로 다 옮겨야함 but circularly 사용하면

저렇게 하면 됨 !!

-> 코드

- 길이 구하는함수