자료구조 - (1) linked list 구현하기

Jaden·2023년 3월 22일

자료구조

목록 보기

1/1

연결 리스트(single linked list)

선형 자료구조이며 같은 데이터형을 가진 데이터를 메모리에 연속적으로 저장하는 배열과 다르게 메모리에 비연속적으로 저장되며 다른 데이터형(data type)을 가진 데이터도 연결될 수 있다.

Q. 데이터들이 메모리에 비연속적으로 존재하는데 어떻게 데이터들을 연결하나?
A. 다음 데이터가 존재하는 메모리 위치를 가리키기 위한 추가적인 메모리 공간을 잡아 저장한다.
즉, linked list는 배열에 비해 메모리를 2배 더 사용한다. 배열은 데이터 저장 공간만 linked list는 데이터 저장 공간 + 다음 주소를 저장하는 공간
그러나 데이터의 삽입 삭제 및 full일 때 관리 속도가 매우 빠르다 즉 제약사항이 없다.,

	메모리 내 저장 방식	메모리 사용량 (상대적)	메모리 사용	관리
배열	연속적인 저장	적음	제약이 많음	데이터 삽입·삭제 시, 복사와 이동이 필요
연결리스트	비연속적인 저장	많음 배열의 2배	제약이 없음 효율적	복사 및 이동할 필요 없이 주소 번지만을 변경

linked list 구현하기

하나의 c 파일 내에서 구조체를 전역으로 정의하고 노드를 추가해본다.
전체 코드 확인한 후, 단계별로 설명한다.

source code

#include <stdio.h>
#include <stdlib.h> // malloc 사용을 위해 필요

//(전역)Node 구조체 정의
struct Node{
	int data;
    struct Node* ptr;
};

//'struct Node'를 'Node'로 줄여 적겠다고 선언
typedef struct Node Node;

//(전역) Node point 타입의 head 선언
struct Node* head;

//main
int main(){
	
	head = NULL;
    
    Node* tmp = (Node*) malloc (sizeOf(Node));
    
    *(tmp).data = 2; 
    *(tmp).ptr = NULL;    
    
    head = tmp;
    Node* tmp1 = tmp; 
    Node* tmp = (Node*)malloc(sizeOf(Node));
    (*tmp).data = 5;
    (*tmp).ptr = NULL;
    tmp1 -> ptr = tmp; 
    
    tmp1 = tmp; //tmp1이 tmp를 가리킴 즉, tmp가 가리키는 곳인

1. Node 구조체 정의

구조체는 데이터를 저장하고 다음 순서의 데이터 위치를 가리키도록 한다.

struct Node{ 
	int data; //데이터
    struct Node* next; //다음 순서의 데이터 위치를 가리키는 next라는 노드 포인트 타입의 변수
}

next는 다음 위치의 노드를 가리키는 변수이다.

Q. 위치라면 int 타입으로 선언해도 되지 않을까?
A. 해도 되지?.... 아니다. 포인트로 가리키는 것이 Node 구조체임을 명시해주기 위함이다. 예를 들어 ++을 사용한다고 할 때, Node 의 크기만큼 넘어가 다음 노드를 가리키게 된다. int였다면 8byte만 이동하여 다른 위치를 가리키고 있을 수도 있다.

2. head 선언

struct Node* head; //전역변수 head 선언 (Node point 타입)

여기서 head는 노드포인트 타입의 변수다.
노드포인트 즉, 노드를 가리키는 변수이므로 노드의 주소를 값으로 가진다.
주소를 값으로 가지므로 구조체포인트 타입의 변수는 4byte다.

#include <stdio.h>
#include <stdlib.h>

//전역으로 Node 구조체 정의
struct Node{ 
	int data;
    struct Node* next;
}

struct Node* head; //전역변수 head 선언 (Node point 타입)



//main함수
int main(){
	head = NULL; 
}

- 여기서 head는 노드포인트 타입의 변수다.
노드포인트 즉, 노드를 가리키는 변수이므로 노드의 주소를 값으로 가진다.
주소를 값으로 가지므로 구조체포인트 타입의 변수는 4byte다.

< 왜 int*가 아닌 Node*로 선언하는가? >
포인트로 가리키는 것이 Node임을 명시해주기 위함

int main(){
	head = NULL;
    
    Node* tmp = (Node*) malloc (sizeOf(Node));
    //tmp는 노드포인트 타입, tmp가 동적으로 할당된 힙영역을 가리킴
}

- tmp라는 변수가, 힙영역의 주소를 값으로 가짐

{width 10000px}

int main(){
	head = NULL;
    Node* tmp = (Node*) malloc (sizeOf(Node));
    
    (*tmp).data = 2; // (*tmp).data == tmp->data
    (*tmp).ptr = NULL;    
}

int main(){
	head = NULL;
    Node* tmp = (Node*) malloc (sizeOf(Node));
    *(tmp).data = 2;
    *(tmp).ptr = NULL;   
    
    head = tmp; //head는 tmp를 가리킴 즉, tmp가 가리키는 곳을 가리킴
}

cf.

틀린 표현	올바른 표현

int main(){
	head = NULL;
    Node* tmp = (Node*) malloc (sizeOf(Node));
    *(tmp).data = 2;
    *(tmp).ptr = NULL;    
    head = tmp;
    
    Node* tmp1 = tmp; // tmp1은 tmp를 가리킴 즉, tmp가 가리키는 곳을 가리킴
}

int main(){
	head = NULL;
    Node* tmp = (Node*) malloc (sizeOf(Node));
    *(tmp).data = 2;
    *(tmp).ptr = NULL;    
    head = tmp;
    Node* tmp1 = tmp;
    
    Node* tmp = (Node*)malloc(sizeOf(Node)); //tmp는 새로 동적할당된 heap영역 가리킴 
}

int main(){
	head = NULL;
    Node* tmp = (Node*) malloc (sizeOf(Node));
    *(tmp).data = 2;
    *(tmp).ptr = NULL;    
    head = tmp;
    Node* tmp1 = tmp; 
    Node* tmp = (Node*)malloc(sizeOf(Node));
    
    (*tmp).data = 5;
    (*tmp).ptr = NULL;
}

int main(){
	head = NULL;
    Node* tmp = (Node*) malloc (sizeOf(Node));
    *(tmp).data = 2;
    *(tmp).ptr = NULL;    
    head = tmp;
    Node* tmp1 = tmp; 
    Node* tmp = (Node*)malloc(sizeOf(Node));
    (*tmp).data = 5;
    (*tmp).ptr = NULL;
    
    tmp1 -> ptr = tmp; //tmp1->ptr은 tmp를 가리킴 즉, tmp가 가리키는 200번지를 가리킴
}

int main(){
	head = NULL;
    Node* tmp = (Node*) malloc (sizeOf(Node));
    *(tmp).data = 2;
    *(tmp).ptr = NULL;    
    head = tmp;
    Node* tmp1 = tmp; 
    Node* tmp = (Node*)malloc(sizeOf(Node));
    (*tmp).data = 5;
    (*tmp).ptr = NULL;
    tmp1 -> ptr = tmp; 
    
    tmp1 = tmp; //tmp1이 tmp를 가리킴 즉, tmp가 가리키는 곳인 
}

위 과정의 반복을 통해 linked list를 구현한다.

(1) for또는 while문을 통해 반복실행하여 노드를 생성하거나; (2) insert함수를 정의하여 노드를 생성할 수 있다.

NEXT POST...
linked list에 데이터 입력하기 - insert( ) 함수

Jaden