chapter 04 연결 리스트(Linked List) 2

#04-1. 연결 리스트의 개념적인 이해 1

공부를 하면서 그림을 그려라. 그림을 그려가면서 이해해야 한다.

동적 할당 malloc, free 함수를 해야 한다는 것은 가정해야 한다.

배열(자료구조)

배열의 가장 큰 장점 

많은 변수를 한 번에 선언할 수 있다.

순차 접근을 하기 위해서 사용한다.

배열의 크기가 결정되어야 한다.

결정 되어진 메모리 형태이다. 

크기, 길이를 결정해야 한다. 순차접근 idx

내가 필요할 때마다 만들고 싶다. 그래서 동적할당이라는 이름이 붙은 것이다. 

연결리스트는 순차 접근을 가능하게 하기 위해서 필요한 것이다.  막 만들어 놓으면 관리가 안된다.

순차적으로 연결하기 위한 것이다. 퍼저 있는 데이터들을 연결하기 위한 것이다. 순차적으로 접근이 가능하다. 헤드만 가리키고 있으면 순차적으로 접근이 가능하다. 연결을 함으로서 가능하다. 머리를 가리키고 시작해서 끝으로 간다. 머리든 끝이든 붙여 나가는 것이다. 확장해 나가는 것이다. 메모리 연결 리스트이다. 연결, 동작할당, 순차적으로 어떻게 접근하기 위한 것인지를 보여준다. 

30%, 60%, 100%..

이 내용을 이해해야 한다. 어떻게 연결을 하지.. 어떻게 순차저으로 접근을 하지..

#04-1. 연결 리스트의 개념적인 이해 2

메모리 덩어리 : 노드라고 한다. 구조체의 변수이다. 

typedef struct _node

{

int data; // 데이터를 담을 공간

struct _node * next; // 연결의 도구

} Node;                    //일종의 바구니, 연결이 가능한 바구니

1) 데이터, 2) 연결

struct _node를 쓸 수 있어??

공개x

허용o

n1.next = &n2;

*(n1.next)

연결이라는 것이 어떻게 완성이 되느냐? 순차적 접근이 어떻게 완성이 되느냐?? 연결이 구조체를 통해서 완성이 되었다. 

head

tail

current 현재

#04-1. 연결 리스트의 개념적인 이해 3

head 연결 리스크의 머리를 가리키기 위한 포인터 변수

tail 연결 리스크의 꼬리를 가리키기 위한 포인터 변수

cur 어떻게 순차적으로 접근하기 위한 포인터다. 

#04-1. 연결 리스트의 개념적인 이해 4

데이터 조회

순차적 접근.

head가 null이 아니면 모든 데이터를 참조할 수 있다.

cur라는 포인터 변수를 이동시킬 수도 있다. 이동 시켜 가리키게 만들 수 있다. 

cur = cur->next

계속 이동하고 이동시켜서 조회하고 출력한다. 

  1

<

  2

노드 참고하는 방법이 나뉜다. 첫 번째 노드를 참조하는 방법, 두 번째 노드를 참조하는 방법.

데이터 삭제

데이터 삭제를 하기 위해서는 포인터 변수 두 개가 필요하다.

#04-1. 연결 리스트의 개념적인 이해 5

데이터 삭제

전체 노드의 삭제 과정

삭제 하고 이동한다. 이게 가능할까?? 가능하지 않다. 

그래서 삭제하려면 노드가 두 개 필요하다. 

delNode, delNextNode를 옮겨가면서 삭제하는 것이다.

장점아니다. 단점이다.

구분 하는 것은 좋지않다. 구분하지 않고 하는 것이 좋다. 

그림의 구조를 바꾸어서 연결리스트를 구현한다.

Dummy node가 등장한다. 삽입, 삭제, 조회를 실행한다.

더미노드가 등장한다..

code  > 그림

code  < 그림

정리하기.

연결 리스트 ADT를 정의하지 않았다.

삽입, 삭제, 조회의 기능이 별도의 함수로 구분되어 있지 않다.

즉 앞서 제시한 코드는 모두 다 main 함수에다 집어넣었기 때문에 필요할 때 가져다 쓸 수 있는 형태가 아니다.

자료구조의 필요성

1. 자료구조의 ADT 정의

2. 정의한 ADT의 구현

3. 구현이 완료된 자료구조의 활용

#04-2. 단순 연결 리스트의 ADT와 구현 1

새 노드의 추가 위치에 따른 장점과 단점

머리에 추가 하는 경우

장점 : tail이 불필요하다.

단점 : 저장된 순서를 유지하지 않는다.

꼬리에 추가하는 경우

장점: 저장된 순서가 유지된다.

단점 : tail이 필요하다.

1 > 2 > 3

3 > 2 > 1

#04-2. 단순 연결 리스트의 ADT와 구현 2

void setsortrule(list * plist, int (*comp)(ldata d1, ldata d2);

                                   반환형 포인터변수 매개변수..

함수 포인터변수.

사용이유? 설치함으로서 리스트의 형동 패턴이 바뀌는 것이다.

기준 함수 반

( d1   d2 )

( 0     1  )

이 내용을 기반으로 구현을 한다.

int whoisprecede(ldata d1, ldata d2) // typedef int ldata;

{

if(d1<d2)

return 0;

else

return 1;

}

#04-2. 단순 연결 리스트의 ADT와 구현 3

연결 리스트의 3개 요소

head 첫 번째 가리키는 포인터 변수

tail

cur

우리가 구현할 더미 노드 기반 연결 리스트

깍두기(더미노드) : 있기만 하지만 유효한 데이터를 담지는 않는 것이다.

삽입, 삭제, 참조. 일관된 패턴을 구성할 수 있다. 

#04-2. 단순 연결 리스트의 ADT와 구현 4

구현하기 전에 그림 그려야 한다.

#04-2. 단순 연결 리스트의 ADT와 구현 5

                        2.    1.

head > dummy > 4 > 6

newnode > 2  3..

#04-2. 단순 연결 리스트의 ADT와 구현 6

before 삭제를 위해서 필요하다. 

before은 cur의 왼쪽에 위치한다. 삭제와 관련되 있다.

before = head

#04-2. 단순 연결 리스트의 ADT와 구현 7

삭제.

cur은 그 이전을 가르켜야 한다. 인쪽을 가리켜야 한다. 

before = cur;

#04-3. 연결 리스트의 정렬 삽입과 구현 1

SetSortRule 함수

comp 특정 주소를 저장 하느냐 마느냐?

SInsert

setsortrule 함수가 호출되면서 정렬의 기준이 리스트의 맴버 comp에 등록되면 sinsert 함수 내에서는 comp에 등록된 정렬의 기준을 근거로 데이터를 정렬하여 저장한다.

#04-3. 연결 리스트의 정렬 삽입과 구현 2

comp가 0을 반환한다는 것은 첫 번째 인자가 data가 정렬 순서상 앞서기 때문에 head에 가까워야 한다는 의미!!

while(pred->next != NULL && plist -> comp(data, pred->next->data) != 0 )

{

pred=pred->next; // 다음 노드로 이동

}

pred의 위치에 따라 달라짐. 

정렬 순서 상 뒤서게 되면 0을 반환하지 않는다.

정렬 순서 상 data가 뒤에 pred드 보다 뒤 서게 되면 0을 반환한다.

pred와 그 다음 노드를 가리키는 사이에   저장 된다.  a(알아야 한다.)        c        b

 

약속

comp가 0을 반환

첫 번쨰 인자인 data가 정렬 순서상 앞서서 head에 더 가까워야 하는 경우

comp가 1을 반환

두 번째 인자인 pred->next->data가 정렬상 앞서서 head에 더 가까워야 하는 경우