LinkedList (1)

 

데이터를 동적으로 할당하는 linkedList에 대해서 알아보기 전에 간단하게  그 컨셉에 대해 구현해보았다.

 

#include<stdio.h>

#include<stdlib.h>

typedef struct _node{

    int data;

    struct _node* next;

}node;

int main(){

    node* head =NULL;

    node* tail =NULL;

    node* cur =NULL;

    node* newnode = NULL;

    int readData;

    //데이터 읽기

    while(1){

        printf("자연수를 입력 하시오 종료하려면 0 입력");

        scanf("%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;

    }

    printf("\n");

    //데이터 출력

    if(head == NULL){

        printf("출력할 데이터가 없습니다.");

    }else{

        cur=head;

        printf("%d\n",cur->data);

        while(cur->next != NULL){

            cur = cur->next;

            printf("%d\n",cur->data);

        }

    }

    printf("\n");

    //메모리 해체//

    if(head == NULL){

        return 0;

    }else{

        node* delnode = head;

        node* del_next = delnode->next;

        printf("%d를 삭제 ",delnode->data);

        free(delnode);

        while(del_next != NULL){

            delnode = del_next;

            //다음꺼 담아뒀다가 다시 delnode에게 줌

            del_next = delnode->data;

            printf("%d를 삭제 ",delnode->data);

            free(delnode);

        }

    }

}

-동적할당 linkedList의 c구현 

 

-데이터를 저장할 node라는 구조체는 다음 노드를 가리키는 next와 데이터를 담을 멤버를 가지고 있다.

- 다음으로 main에 노드에 데이터를 추가하고, 삭제하고, 출력하는 과정을 구현하였다.

 

1. 데이터 추가

 

>데이터를 담은 newnode 생성

 

-첫 데이터 추가- 

>head에 아무런 데이터가 없다면, head = newnode 

>tail도 newnode를 가리키게 되면서 head=tail은 같다.

 

-다음 데이터 추가-

>기존 tail->next를 newnode와 연결한다.

> tail =newnode가 되면서 배열의 끝을 계속 지정한다.

출처:https://velog.io/@yeonjuu417/Linked-List-Hash-Table

2. 데이터 출력

 

> node 포인터 cur이 head를 가리키게 한다.

> 첫 데이터를 출력하고 > cur = cur->next를 계속하면서 cur->next가 null이 될 때까지 반복한다.

 

3. 데이터 삭제

> delnode가 head를 가리키게 한다. 

> delnext가 head->next를 가리키게한다.

>첫 데이터 삭제 후 delnext가 null까지 delnode = delnext, delnext = delnext->next를 반복한다.

 

*바로 head를 삭제하고 head = head->next를 하지 못하는 이유는 이미 head가 가리키는 node를 free하면, head->next도 접근할 수 없게되므로, 두 변수를 따로 추가해서 삭제한다.

 

->자바를 이용한 구현

import java.util.Scanner;

class node<T>{
    private T data;
    private node next;

    public node(T data, node next){
        this.data = data;
        this.next = next;
    }
    public void setNext(node next){
        this.next = next;
    }
    public void setData (T data){
        this.data = data;
    }
    public T getdata() {return this.data; }
    public node getNode() {return  this.next;}

}


public class ListTEST1 {

    public static void main(String[] args){
        Scanner sc =new Scanner(System.in);
        node<Integer> head = null;
        node<Integer> tail = null;
        node<Integer> cur =null;
        node<Integer> newnode;

        while(true){
            System.out.print("숫자를 입력하세요 종료하려면 0 : ");
            int x;
            if((x=sc.nextInt()) == 0) break;
            newnode = new node<>(x,null);

            if(head == null){
                head=newnode;
            }else {
                tail.setNext(newnode);
            }
            tail  = newnode;
        }

        //데이터 출력
        System.out.print("입력 받은 데이터 전체 출력");
        System.out.println();
        if(head == null) System.out.print("출력할 데이터가 없습니다.");
        else {
            cur = head;
            System.out.print(cur.getdata()+" "); //newnode가 1개일 수 있음
            while(cur.getNode() != null){
                cur = cur.getNode();
                System.out.print(cur.getdata()+" ");
            }
        }
        System.out.println();

        //메모리 해체과정
        if(head ==null) return;
        else{
            node<Integer> deleteNode = head;
            node<Integer> delNext = head.getNode();
            System.out.printf("%d 데이터를 삭제합니다.\n",deleteNode.getdata());
            deleteNode =null;
            while(delNext != null){
                deleteNode = delNext;
                delNext = delNext.getNode();
                System.out.printf("%d 데이터를 삭제합니다.\n",deleteNode.getdata());
                deleteNode =null;

            }

        }


    }


}

 

 

-참고자료 : 열혈자료구조 - 윤성우

 

https://velog.io/@yeonjuu417/Linked-List-Hash-Table

[Data Structure]Linked List