Linked list (연결 리스트) 란 무엇인가?

Linked list (연결 리스트)

 

 

간단히 설명하자면 고구마 줄기라고 생각해봐라.

 

처음 시작하는 부분만 알고 있다.

 

그 시작 부분을 타고 들어가다 보면 고구마(data)가 계속 줄줄이 나온다.

 

시작(주소) - 연결(link) - 끝(null pointer or circular)

 

위의 순서가 존재함을 기억해라.

 

singly linked list (chain)

 

연결 리스트는 위의 그림과 같이 여러개의 node(노드)를 연결함으로써 데이터를 표현가능하다.

 

노드는 자료를 가진 data 부분과 다음 노드를 연결하는 link 부분으로 나뉘어져 있다.

 

배열과 유사하지만 훨씬 효율적인 저장 방법이다.

 

	Array (배열)	Linked list (연결 리스트)
차이점	- static allocation of array (정적할당)     - 정해진 메모리크기를 미리 할당 하기때문에 오버플로우나 공간 낭비가 발생가능하다.	- dynamic allocation of memory(nodes)      (동적할당)     - 필요한 만큼 메모리를 동적으로 할당 받아서 만든다.

 

---

연결리스트의 여러 종류

 

 

•  Singly linked list

 

•  Circularly linked list

         :  마지막 노드가 다시 처음 노드를 가리킴.

•  List with a header node

        :  노드 맨앞에 head node 를 넣어 삽입, 삭제 등 연산에서 이점을 만듬.

 

 

•  Doubly linked list (양방향 연결리스트)

        :  노드를 연결하는 link가 앞 뒤로 존재해서 앞 뒤 노드들 간의 관계를 바로 확인할 수 있다.

 

---

Node 를  C 언어로 표현하기 위한 자료형 선언

 

 

아래의 선언은 자기 참조 구조의 예를 포함하고 있다.

 

C 는 아직 존재하지 않는 타입에 대한 포인터의 생성을 지원한다.

 

그렇기 때문에 조금 이상하게 보이겠지만,

 

구조체 타입을 정하기 전에도 그 구조체에 대해서 포인터 생성이 가능하다.

 

typedef struct listnode *nodePtr; 
	// nodePtr 자기 자신을 가리키는 pointer 를 먼저 선언해준다.

typedef struct listnode {
    int data; // declaration of data fields
    nodePtr link; // declaration of link field
};

 

 

예시) 다항식 자료형 선언

 

typedef struct polynode *polyPointer;
typedef struct polynode{
    int coef; // 계수
    int expon; // 지수
    polyPointer link; // 링크 연결 부분.
};

 

---

연결 리스트의 생성

 

시작 - 연결 - 끝 주소와 구조체에 주목해서 다음 예시를 보자.

 

예시 ) 두개의 노드를 가진 연결 리스트의 생성

 

malloc 함수를 통해서 얻은 값은 메모리 주소를 나타내는 포인터이다. (아래 그림에서 first)

 

그 포인터가 가리키는 메모리에 데이터를 넣기위해서는 구조체를 이용한다.

 

first->data = 10;

 

다음 노드를 연결하는 링크에는, 다음 노드의 시작 메모리 주소를 넣어준다.

 

first->link = second;

 

typedef struct listnode *listPointer; 
typedef struct listnode {
    int data; // declaration of data fields
    listPointer link; // declaration of link field
};

listpointer create2()
{	/* 2개의 노드를 가진 연결 리스트를 만드는 함수*/
    listpointer first, second;
    
    first = (listPointer)malloc(sizeof(*first)); 
    	// malloc 을 사용하여 필요한 메모리를 할당한다.
        // memory 공간을 가리키는 시작 주소를 리턴한다.
        // (listPointer)은 typecast로서 할당하는 데이터의 타입을 말한다.
        
    second = (listPointer)malloc(sizeof(*second));
    
    second.link = NULL; 
    second.data = 20;
    first.data = 10;
    first.link = second; // 두번째 노드에 연결한다.
    
    return first; // 만든 연결 리스트의 시작 부분인 포인터를 반환한다.
}

 

예시 2 ) list of words

 

 

#include <string.h>
#include <stdio.h>

typedef struct listnode *listPointer; 
typedef struct listnode {
    char data[4]; // 문자열 데이터 표현, end of string 도 생각해준다.
    listPointer link; // declaration of link field
};

listpointer create()
{	
    listpointer first
    
    first = (listPointer)malloc(sizeof(*first)); 
    	// malloc 을 사용하여 필요한 메모리를 할당한다.
        // memory 공간을 가리키는 시작 주소를 리턴한다.
        // (listPointer)은 typecast로서 할당하는 데이터의 타입을 말한다.
        
    
    first.link = NULL; // fisrt 포인터가 가리키는 구조체의 link 포인터
    strcpy(first.data, "cat");
    
    return first; // 만든 연결 리스트의 시작 부분인 포인터를 반환한다.
}