[ 자료구조 ] 단순 연결 리스트

[ 자료구조 ] 단순 연결 리스트

 

Heap 영역은 공유되는 영역으로 동적 할당 공간을 만든다.

연결 리스트는 이렇게 동적 할당된 방법을 사용한다. 

동적 할당된 방법을 사용하면 원하는 크기를 할당할 수 있어 효율적이다.

단순 연결 리스트를 활용하면 데이터를 움직이지 않는다는 장점이 있다.

 

단순 연결 리스트

 

연결 리스트의 가장 간단한 형태로 그냥 연결 리스트라고 부르기도 하고 단일 연결 리스트라고 부르기도 한다.

노드들을 연결한 형태이며 노드는 데이터 부분과 링크 부분으로 구성된다.

데이터 부분은 한 개 혹은 여러 개의 속성을 저장할 수 있다. 링크 부분은 다음 노드의 주소 값을 가리킨다.

동적 기억 할당과 해제가 가능하다. 동적 해제는 free 함수를 사용한다.

 

간단하게 데이터를 노드라고 부르기도 한다.

 

list_ptr ptr = NULL;
//struct node * ptr = NULL;

ptr = (list_ptr)malloc(sizeof(list_node));
//ptr = (struct node *)malloc(sizeof(list_node));

ptr->data = 50;
ptr->link = NULL;

list_ptr ptr = NULL;
//struct node * ptr = NULL;

ptr = (list_ptr) malloc(sizeof(list_node));
//ptr = (struct node *) malloc(sizeof(list_node));

ptr->data = 50;
ptr->link = NULL;

 

 

형 변환

 

명시적 형 변환을 위해 우리는 괄호 안에 자료형을 넣어 표현한다.

 

(int * ) p;  // p의 자료형을 정수형 포인터로 바꾼다.

(struct node *) p; // p의 자료형을 구조체 포인터로 바꾼다.

 

 

728x90

 

 

단순 연결 리스트와 삽입 알고리즘

새로운 주소 값 포인터를 정의해 동적 할당한다.

동적 할당된 공간에 추가할 데이터와 포인터를 넣는다.

새로 추가된 포인터가 자신이 삽입될 공간 바로 뒤에 있는 노드의 데이터를 가리킨다.

삽입할 연결 리스트의 앞 노드의 포인터가 삽입할 데이터를 가리킨다.

 

30과 70 사이에 50을 삽입한다고 가정하자.

 

1. 기억 장소로부터 노드를 얻는다. 이때 노드 주소 값을 변수 paddr에 저장한다.

2. 노드에 50 데이터를 저장한다

3. "paddr" 노드의 링크 값에 30 노드의 링크 값을 저장한다.

4. 30 노드의 링크 값에 paddr을 저장한다.

5. paddrd을 동적 해제한다.

 

 

728x90

 

 

단순 연결 리스트와 삭제 알고리즘

 

삭제할 노드의 앞 노드를 찾고, 삭제할 노드의 링크 부분에 있는 주소 값을 앞 노드에게 전달한다.

따라서 삭제할 노드 앞 노드에는 삭제할 노드 뒤 노드 데이터를 가리킨다.

1. 삭제할 50 노드의 앞 노드 30을 찾는다.

2. 앞 노드의 링크가 가리키는 곳을 50 노드의 링크가 가리키는 곳으로 바꾼다.

 

 

연결 리스트의 생성 함수 (정수형 데이터 저장, 리스트 포인터 반환)

 

list_ptr create(){

    list_ptr first, second;

    first = (list_ptr)malloc(sizeof(list_node));
    second = (list_ptr)malloc(sizeof(list_node));
    second->link = NULL;
    second->data = 20;
    first-> data = 10;
    first-> link = second; // first가 second의 데이터를 가리키도록한다.
    
    return first; // 첫번째 노드만 반환해줘도 된다.
    
}

list_ptr create(){

    list_ptr first, second;

first = (list_ptr) malloc(sizeof(list_node));
    second = (list_ptr) malloc(sizeof(list_node));
    second->link = NULL;
    second->data = 20;
    first-> data = 10;
    first-> link = second;
    
    return first;
    
}

 

 

728x90

 

 

 

// list_ptr 자료형으로 함수를 생성한다.

// first, second 포인터를 선언한다.

// first, second 포인터가 가리키는 동적 할당된 영역을 생성한다.

// second(마지막 영역)이 가리키는 곳에 NULL을 대입한다.

// second 동적 할당된 영역의 데이터에 20을 넣는다.

// first 동적 할당된 영역의 데이터에 10을 넣는다.

// first의 링크가 second를 참조하도록 한다.

 

첫 번째 포인터를 반환해준다. 이것은 HEAD이며 첫 번째 list_ptr 즉 구조체 포인터만 전달해줘도 된다.