알고리즘 기초 2 - [자료구조, 단일링크드리스트(삽입, 삭제, 검색)]

알고리즘 메모리와 주소, 자료형과 자료구조

목차

메모리와 주소의 관계

Simple Question

• 프로그램 안에서 데이터를 저장하거나 저장된 데이터를 불러올 때, 메모리에 어떻게 접근할까?

  
  

    - 보통은 메모리의 위치정보가 있는 "메모리 주소"를 통해 접근한다 (C, C++에서는 Pointer)

프로그램의 효율성 측면에서 볼 때, 배열이 담고 있는 각각의 집이라면, 'A'라는 친구의 집을 찾아갈 때, 0번지부터 끝번지까지 집 문앞에서 문을 두드려 주인을 확인하는 방법이 빠를까? 아니면 이미 'A'라는 친구의 집주소를 알고 그 집으로 한번에 찾아가는 것이 빠를까?

 

자료형과 자료구조

Simple Question

• 프로그래밍 언어에서 별도의 자료형(type)을 제공하는 이유는 무엇일까?

 

    1. 메모리 공간의 효율적 이용
    2. 메모리를 효율적으로 사용하는 자료구조 구축

 

저장하려는 값의 범위가 제한적일 때, 그 값을 담을 수 있는 바이트의 크기를 제한하는 것은 메모리 누수를 예방하기 위한 탁월한 선택이다. 또한, 연속적인 값을 담고자 할 때, 그 참조를 간단한 주소의 연산과 함께 쉽게 얻을 수 있는 자료구조를 구축한다면 메모리에 값을 쉽게 저장하고 읽을 수 있다.

기본적인 자료구조

 

Linked List

• 프로그램 실행 중 새로운 노드 삽입, 삭제가 간편하며 링크라는 개념을 통해 물리 메모리를 연속적으로 사용하지 않아도 되어 관리하기 쉽다.
• 데이터를 구조체로 묶어 포인터로 연결할 수 있다는 장점이 있다.

 

• [노드]-링크-[노드]-링크-[노드]
  • [헤드 노드]-링크-[노드]- ... -링크-[엔드 노드]

 

    - 각각의 노드의 번호에 맞게 자리를 찾아가기 위해서는, 각 자리를 찾아 갈 수 있도록 연결된 노드들에 의미를 부여해주어야 한다.
    - 이 역할을 '헤드노드'가 부여한다. 각 노드는 헤드노드를 기준으로 번호를 찾아 자리를 찾아갈 수 있다.
        - 헤드 노드에는 데이터를 저장하지 않는다. 링크드 리스트의 시작 부분임을 나타낼 뿐이다. 
    - 또한, 링크드 리스트의 마지막 부분을 나타내는 노드가 있는데, 이를 'End Node' 또는 'Tail Node'라고 부른다.
        - 이 역시 데이터를 저장하지 않고, 링크드 리스트의 끝 부분을 나타내는 기준선이 된다.

 

단일 링크드 리스트 구조

 

C

    typedef struct _Node {
        char Data;
        struct _Node *Next;
    } Node;

 

Java

    class Node {
        private char data;
        Node next;
    }

 

JavaScript

class  Node {
    constructor(data) {
        this.data = data;
        this.next = null;
    }
}

 

단일 링크드 리스트의 삽입과 삭제

• 단일 링크드 리스트의 특징

  • 단일 링크드 리스트의 장점 = 배열의 단점

    • 단일 링크드 리스트와 배열의 특성은 특정 자료형의 연속적인 데이터를 저장한다는 것이다.

    • 다만, 배열은 생성될 때 데이터를 저장하는데 모든 메모리를 확보해 사용 가능하도록 해주므로, 프로그램 실행 중간에 배열의 크기를 변경할 수 없다.

    • 배열 안에 저장되어 있는 값들을 정렬할 때에도 메모리에 저장되어 잇는 각각의 값을 바꿔주어야 한다.

    • 단일 링크드 리스트는 위와 같은 배열의 단점을 해결하여 준다.

      • 배열은 연속된 메모리를 사용하지만 링크드 리스트는 반드시 연속적이라고 볼 수는 없다.

단일 링크드 리스트의 삽입(검색),삭제(검색) 알고리즘

C

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

typedef struct _Node {
    char Data;
    struct Node *Next;
} Node;

Node *head, *end, *temp;
Node *temp1, *temp2, *temp3;

void Initialize(void);
void InserrNode(Node *);

void Initialize(void)
{
    Node *ptr;
    head = (Node *)malloc(sizeof(Node));
    end = (Node *)malloc(sizeof(Node));

    temp1 = (Node *)malloc(sizeof(Node));
    temp1->Data = 'A';
    head->Next = temp1;
    temp1->Next = end;
    end->Next = end;
    ptr = temp1;

    temp2 = (Node *)malloc(sizeof(Node));
    temp1->Data = 'B';
    ptr->Next = end;
    temp2->Next = end;
    ptr = temp2;

     temp3 = (Node *)malloc(sizeof(Node));
     temp3->Data = 'D';
     ptr->Next = temp3;
     temp3->Next = end;
     ptr = temp3;
}

void InsertNode(Node *ptr)
{
    Node *indexPtr;

    for(indexPtr = head; indexPtr != end; indexPtr = indexPtr->Next) {
        if(indexPtr->Next->Data > ptr->Data)
            break;
    }

    ptr->Next = indexPtr->Next;
    indexPtr->Next = ptr;
}

void DeleteNode(Node *ptr)
{
    Node *indexPtr;
    Node *deletePtr;

    for(indexPtr = head; indexPtr != end; indexPtr = indexPtr->Next) {
        if(indexPtr->Next->Data == ptr->Data) {
            deletePtr = indexPtr->Next;
            break;
        }
    }

    indexPtr->Next = IndexPtr->Next->Next;
    free(deletePtr);
}

void main()
{
    Node *ptr;
    int i = 0;
    Initialize();

    // 링크드 리스트의 노드에 저장한 데이터 출력
    ptr = head->Next;

    for(int i=0; i<3; i++) {
        printf("%2c", ptr->Data);
        ptr = ptr->Next;
    }

    // 새로온 노드 생성
    printf("\n");
    temp = (Node*)malloc(sizeof(Node));
    temp->Data = 'C';

    // 새로 생성한 노드 삽입
    InsertNode(temp);

    // 링크드 리스트의 노드에 저장한 데이터 출력
    ptr = head->Next;

    for(int i=0; i<4; i++) {
        printf("%2c", ptr->Data);
        ptr = ptr->Next;
    }

    deletePtr('D');
    for(int i=0; i<3; i++) {
        printf("%2c", ptr->Data);
        ptr = ptr->Next;
    }
}
// 결과
// 1. A B D
// 2. A B C D
// 3. A B C

 

Java

public  class  SingleLinkedList {

    static  class  Node {
        char  data;
        Node  Next;

        public  Node(char  data) {
            this.data = data;
            this.Next = null;
        }
    }



    public  static  Node  head, end;
    public  static  Node  temp1, temp2, temp3, ptr;

    public  static  void  Initialize() {
        head = new  Node('H');
        end = new  Node('E');
        end.Next = end;

        temp1 = new  Node('A');
        head.Next = temp1;
        temp1.Next = end;
        ptr = temp1;

        temp2 = new  Node('B');
        ptr.Next = temp2;
        temp2.Next = end;
        ptr = temp2;

        temp3 = new  Node('D');
        ptr.Next = temp3;
        temp3.Next = end;
        ptr = temp3;
    }



    public  static  void  InsertNode(Node  node) {
        Node  indexPtr;
            for(indexPtr = head; indexPtr != end; indexPtr = indexPtr.Next) {
                if(indexPtr.Next.data > node.data)
                    break;
            }

        node.Next = indexPtr.Next;
        indexPtr.Next = node;
    }

    public static void DeleteNode(Node node) {
        Node indexPtr;
        for(indexPtr = head; indexPtr != end; indexPtr = indexPtr.Next) {
            if(indexPtr.Next.data == node.data)
                break;
        }

        indexPtr.Next = indexPtr.Next.Next;
    }

    public  static  void  main(String[] args) {
        Node  node;
        Node  temp;

        int  i = 0;
        Initialize(); 

        // 링크드 리스트의 노드에 저장한 데이터 출력
        node = head.Next;

        for(i=0; i<3; i++) {
            System.out.print(String.format("%2c", node.data));
            node = node.Next;
        }

        // 새로온 노드 생성
        System.out.println();
        temp = new  Node('C');

        // 새로 생성한 노드 삽입
         InsertNode(temp);

        // 링크드 리스트의 노드에 저장한 데이터 출력
        node = head.Next;
        for(i=0; i<4; i++) {
            System.out.print(String.format("%2c", node.data));
            node = node.Next;
        }
        System.out.println();

        // 노드 삭제
        temp = new Node('D');
        DeleteNode(temp);
        node = head.Next;
        for(i=0; i<3; i++) {
            System.out.print(String.format("%2c", node.data));
            node = node.Next;
        }
    }
}
// 결과  
// 1. A B D  
// 2. A B C D
// 3. A B C

 

JavaScript

class  Node {
    constructor(data) {
        this.data = data;
        this.next = null;
    }
}



let  head, end;
let  temp, temp1, temp2, temp3, ptr;

const  Initialize = () => {
    head = new  Node(null);
    end = new  Node(null);
    end.next = end;

    temp1 = new  Node('A');
    head.next = temp1;
    temp1.next = end;
    ptr = temp1;

    temp2 = new  Node('B');
    temp1.next = temp2;
    temp2.next = end;
    ptr = temp2;

    temp3 = new  Node('D');
    temp2.next = temp3;
    temp3.next = end;
    ptr = temp3;
}

const  InsertNode = (node) => {
    let  indexPtr;
    for(indexPtr=head; indexPtr.next != end; indexPtr = indexPtr.next) {
        if(indexPtr.next.data > node.data)
            break;
    }
    node.next = indexPtr.next;
    indexPtr.next = node;
}

const DeleteNode = (node) => {
    let indexPtr;
    for(indexPtr = head; indexPtr.next != end; indexPtr = indexPtr.next) {
        if(indexPtr.next.data == node.data)
            break;
    }
    indexPtr.next = indexPtr.next.next;
}

const  main = () => {
    let node;  
    let i = 0;
    let ret1 = "";
    let ret2 = "";
    let ret3 = "";

    Initialize();
    node = head.next;
    for(i=0; i<3; i++) {
        ret1 += ` ${node.data}`;
        node = node.next;
    }
    console.log(ret1);

    temp = new  Node('C');
    InsertNode(temp);
     node = head.next;

    for(i=0; i<4; i++) {
        ret2 += ` ${node.data}`;
        node = node.next;
    }
    console.log(ret2);

    temp = new  Node('D');
    DeleteNode(temp);
    node = head.next;
    for(i=0; i<3; i++) {
        ret3 += ` ${node.data}`;
        node = node.next;
    }
    console.log(ret3);
}

main();
// 결과  
// 1. A B D  
// 2. A B C D
// 3. A B C

 

NOTE | 단일 링크드 리스트에서 1개의 노드를 삽입하는 과정

1. 새로운 노드를 생성한다.

   Node *ptrNode = (Node *)malloc(sizeof(NODE));

2. 새로운 노드가 삽입될 위치를 검색한다.

   for(indexPtr = head; indexPtr != end; indexPtr = indexPtr->Next) {
    if(indexPtr->Next->Data > ptr->Data)
        break;
    }

3. 새로운 노드의 Next를 새로운 노드가 삽입될 다음 노드로 연결한다.

   ptr->Next = indexPtr->Next;

4. 새로운 노드가 삽입될 위치의 이전 노드의 Next가 새로운 노드를 가리키도록 한다.

   indexPtr->Next = ptr;

 

NOTE | 단일 링크드 리스트에서 1개의 노드를 삭제하는 과정

1. 이전 노드를 가리킬 포인터와 삭제할 노드를 가리킬 포인터를 선언한다.

   Node *indexPtr;
   Node *deletePtr;

2. 삭제할 노드를 검색한다.

   for(indexPtr = head; indexPtr != end; indexPtr = indexPtr->Next) {
   if(indexPtr->Next->Data == ptr->Data) {
       deletePtr = indexPtr.Next;
       break;
   }        
   }

3. 이전 노드가 삭제할 노드를 건너뛰고 다음 노드를 가리키도록 링크를 새로 설정한다.

   indexPtr->Next = indexPtr->Next->Next;

4. free() 함수로 삭제할 노드를 실제 메모리에서 삭제한다.

   indexPtr->Next = ptr;