[자료구조]04.연결리스트(Linked List)

0204~0206 복습.

 

01.

배열: 순차접근(idx)이 가능하지만 크기가 결정되면 변경 못하는 자료구조.

 

Q. 요청시마다 메모리할당 하고싶은데?

A. malloc으로 가능, 그렇지만 관리는 불가.

=연결리스트(ADT)

 

A - B - C - D - E --->[ + ]

A에 접근이 되면 C도 접근이 가능하다.(순차적으로 접근이 가능하다)

또 확장도 가능함.

 

*malloc은 메모리할당방법(동적할당), 연결리스트는 관리방법이다.

 

 

 

typedef struct_node{
    int data; // 데이터 담을공간
    struct _node *next; //연결의 도구
} Node;
 
int main(void){
    Node *head = NULL;
    Node *tail = NULL;
    Node *cur = NULL;
 
    Node *newNode = NULL;
    int readData;
    ...
}

Node는 기본자료형으로 정의가 안되서 구조체로 정의한다.

데이터를 담을수 있는 메모리 공간이 있어야하고 연결이 가능해야 한다.

 

struct _node *next; 노드의 변수를 가리킬수 있는 포인터변수.

ex) data1의 next = data2 의 주소

data1.next = &data2;

*(data1.next) = B이다.

 

 

 

02.

데이터 추가

 

 

head : 첫번째 노드를 가르킨다.

tail : 마지막 노드를 가르킨다.

둘다 처음엔 NULL.

while(1){ //*01 
     printf("자연수 입력:");
    scatnf("%d", &readData);
    if(readData<1)
    break;
    
    //노드의 추가과정
    newNode = (Node*)malloc((sizeof)Node);
    newNode->data = readData;
    newNode->next = NULL;
 
    if(head==NULL)
        head = newNode;
    else
        tail->next = newNode;
 
    tail = newNode;
}
 

 

*01. while 문은 원하는만큼 노드를 생성하기 위해서.

 

1) 2입력 _ 8~16

[head]→[2|NULL]←[tail]

 

2) 3입력

[head]→[2|NULL]→[3|NULL]

     ↑[tail]

 

3) 2의 next에 3의 주소 입력, : tail->next = newnode == 2->next = &3

[head]→[2|next]→[3|NULL]

      ↑[tail]

 

tail->next 는 tail이 가르키는 노드의 next. tail 이 가르키는 노드는 2.

2의 next에 3의 주소가 들어가야 하니까, tail->next = newNode;

 

4)tail 이동 : tail = newNode;

[head]→[2|next]→[3|NULL]

  ↑[tail]

 

 

 

03.

데이터 조회

 

if(head==NULL){
    printf("저장한 자연수가 없음.\n");
}
else{
    cur = head;
    printf("%d", cur->data);
    while(cur->next != NULL){
        cur = cur->next;
    }
}

 

cur: 내가 어디까지 순차접근했는지.

2(cur)를 조회한다 - 4로 넘어가야함 : cur가 2의 next(cur->next)를 받아 4로 이동 - 4 조회

 

 

 

04.

데이터 삭제

노드의 전체삭제 과정: 포인터가 2개는 필요하다

 

 

if(head==NULL){
    return 0;
}
else{
    Node *delNode = head;  
    Node *delNextNode = head->next; //head가 가르키는 것의 next
    printf("%d을 삭제\n", head->data);
    free(delNode);
 
    while(delNextNode !=NULL){
        delNode = delNextNode;
        delNextNode = delNextNode->next;
        printf("%d을 삭제\n", delNode->data);
        free(delNode);
    }
}

 

 

1) *dN = head(head가 가지고 있는값), *dNN = head->next(head가 가르키는 것의 next = 다음노드)

2) dN을 삭제하고 dN에는 dNN의 주소 넣음.

3) dN옆으로 이동, dNN도 한칸 옆으로 이동.

4) dN 삭제, dN에 다음노드인 dNN의 주소 넣음.

5) 옆으로 한칸씩 이동.

... 반복

 

dN이 가르키는 노드가 삭제되어도 dNN이 다음 노드를 가르키고 있으니까 이전거는

부담없이 삭제(free)가 가능하다.

 

 

 

05.

단순연결리스트의 ADT와 구현

 

배열리스트의 ADT와 연결리스트의 ADT나 달라지는게 없다.

내부구현에 따라 달라지지 않는다.(기능에 따른 함수가 있을수는 있다.)

 

새 노드를 head에 추가하면 : tail이 불필요하다, 저장된 순서가 유지되지 않는다.

새 노드를 tail에 추가하면 : tail이 필요하다, 순서가 유지된다.

 

정렬기능 추가: SetSortRule함수

 

*comp : 포인터 변수선언

왼쪽 반환형, 오른쪽의 매개변수 선언을 갖고 있는 함수의 주소값

int : 반환형

LData d1, LData d2 : 매개변수 선언

= 반환형이 int이고 LData형 인자를 두 개 전달받는 함수의 주소값 전달

 

정렬조건: 뭘넣느냐에 따라 달라짐.

 

Q. 내림차순 하고 싶어

A. if(d1>d2)

정렬기준 : 함수 d1, d2

Q. 3넣을거야

A. 함수 호출해서 기준반환값으로 판단.

Q.리스트에 정렬기준 장착할거야

A.부품이 함수(조건만족시켜라)

 

 

 

06.

더미노드 추가

 

더미노드: 유효한데이터가 아니다(실제의미 없음.), 2번째 이후 노드부터 삽입한다.

head에 새 노드를 추가할때 더미노드가 없는 경우, 1,2번째 이후의 노드추가 방식/삭제방식이 다를수 있다.

 

 

 

07.

더미 연결리스트의 구조체

typedef struct _node{
    LData data;
    struct _node *next;
} Node; //노드의 구조체 표현
 
-------------------------------------
 
typedef struct _linkedlist{
    Node *head; //더미 노드를 가리키는 멤버
    Node *cur; //참조, 삭제 돕는 멤버
    Node *before; //삭제 돕는 멤버
    int numOfData; //저장된 데이터의 수
    int (*comp)(LData d1, LData d2); //정렬의 기준을 등록하기 위한 멤버
    //comp: 설치를 위한 함수포인터 변수
}LinkedList;

 

 

08.

더미 연결리스트 구현_초기화

 

 

 

09.

더미 연결리스트 구현_ 삽입

 

 

 

 

 

plist->head

ex)List L1, L2 --> &L1, &L2

L1, L2가 전달된 연결리스트의 헤드

== DMY (더미)

 

0)생성

Node *newNode= (Node*)malloc(sizeof(Node));

newNode->data = data; //유효데이터 저장

 

1)더미의 Next를 2에 저장.

newNode->next= plist->head->next;

head가 가르키는 것의 Next = DMY의 Next = 4의 주소

 

2) DMY에는 newNode 2의 주소 저장

plist->head->Next  = newNode;

 

 

 

 

10.

참조

 

plist->cur = head->next

head가 가르키는 것의 next = DMY의 next

 

 

 

 

 

11.

삭제

LData LRemove(List *plist){
    Node *rpos = plist->cur;
    Ldata radata = rpos->data;
    
    plist->before->next = plist->cur->next;
    plist->cur = plist->before;
 
    free(rpos);
    (plist->numOfData)--;
    return rdata;
}

before: 노드의 삭제진행을 위함. 삭제진행을 위해서는 두개의 포인터 변수가 필요해서.

 

 

1) before에 삭제할 데이터(cur)의 next저장

plist->before->next = plist->cur->next;

 

2)cur 를 before로 이동

 

그리고 삭제.

삭제후 before와 cur가 겹치는 건 LNext, LFirst때 재조정 되니까 신경쓰지 않아도된다.

 

LN, LF호출되면 LRemove 1번, LR은 연속호출 안됌.