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

이중 링크드 리스트

목차

단일 링크드 리스트는 배열처럼 오직 한 방향으로만 순회하여 참조 가능한 자료구조이지만,
이중/원형 링크드 리스트는 전의 요소를 순회 혹은 이전 노드로 이동하여 참조가 가능한 자료구조이다.

[참조] 달달한 디버깅

 

이중 링크드 리스트 구조체 정의

C

typedef struct _NODE {
    char Data;
    struct _Node *Next;
    struct _Node *prev;
} NODE;

 

Java

class Node {
    char data;
    Node next;
    Node prev;

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

 

JavaScript

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

 

이중 리스트의 삽입과 삭제 알고리즘

C

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

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


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

void Initalize(void);
void InsertNode(NODE *);
void DeleteNode(Node *);

void Intialize(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;
    temp1->Prev = head;
    end->Next = end;
    ptr = temp1;

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

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

void InsertNode(NODE *ptr) {
    NODE *indexPtr;
    for(indexPtr = head->Next; indexPtr != end; indexPtr = indexPtr->Next) {
        if(indexPtr->Data < ptr->Data && indexPtr->Next->Data > ptr->Data) break;
    } 
    ptr->Next = indexPtr->Next;
    indexPtr->Next->Prev = ptr;
    indexPtr->Next = ptr;
    ptr->Prev = indexPtr;
}


void DeleteNode(NODE *ptr) {
    NODE *indexPtr;
    NODE *deletePtr;
    for(indexPtr = head->Next; indexPtr != end; indexPtr = indexPtr->Next) {
        if(indexPtr->Data == ptr->Data) {
            deletePtr = indexPtr;
            break;
        }
    }
    indexPtr->Prev->Next = indexPtr->Next;
    indexPtr->Next->Prev = indexPtr->Prev;
    free(deletePtr);
}

void main()
{
    NODE *ptr;
    int i = 0;
    Intialize();

    // 링크드 리스트의 노드에 저장된 데이터 출력
    printf("노드 C의 삽입 전\n");
    ptr = head->Next;

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

    // 삽입할 새로운 노드 생성
    temp = (NODE*)malloc(sizeof(NODE));
    temp->Data = 'C';
    InsertNode(temp);

    //링크드 리스트의 노드에 저장된 데이터 출력
    pritf("노드 C의 삽입 후\n");
    ptr = head->Next;
    for(i=0; i<4; i++) {
        printf("%2c", ptr->Data);
        ptr = ptr->Next;
    }
    prntif("\n");

    // 노드의 삭제
    DeleteNode(temp);
    pritf("노드 C의 삽제 후\n");
    ptr = head->Next;
    for(i=0; i<3; i++) {
        printf("%2c", ptr->Data);
        ptr = ptr->Next;
    }
    prntif("\n");
}
// 결과
// 노드 C의 삽입 전
// A B D
// 노드 C의 삽입 후
// A B C D
// 노드 C의 삭제 후
// A B D

 

Java

class  DoubleLinkedList {
    static  class  Node {
        char  data;
        Node  prev;
        Node  next;

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

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

    public  static  void  initialize() {
        Node  ptr;
        head = new  Node('H');
        end = new  Node('E');

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

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

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

public  static  void  insertNode(Node  node) {
    Node  indexPtr;
    for(indexPtr=head.next; indexPtr != end; indexPtr = indexPtr.next) {    
        if(indexPtr.data < node.data && indexPtr.next.data > node.data) break;
    }
    node.next = indexPtr.next;
    indexPtr.next.prev = node;
    indexPtr.next = node;
    node.prev = indexPtr;
}

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

    indexPtr.next.prev = indexPtr.prev;
    indexPtr.prev.next = indexPtr.next;
}

public  static  void  main(String[] args) {
        Node  ptr;
        String  ret = "";
        int  i = 0;

        initialize();
        ptr = head.next;

        for(i=0; i<3; i++) {
            ret += String.format(" %c", ptr.data);
            ptr = ptr.next;
        }
        System.out.println(ret);

        ret = "";
        temp = new  Node('C');
        insertNode(temp);
        ptr = head.next;

        for(i=0; i<4; i++) {
            ret += String.format(" %c", ptr.data);
            ptr = ptr.next;
        }
        System.out.println(ret);

        ret = "";
        deleteNode(temp);
        ptr = head.next;
        for(i=0; i<3; i++) {
            ret += String.format(" %c", ptr.data);
            ptr = ptr.next;
        }
    System.out.println(ret);
    }
}
// 결과
// 1. A B D
// 2. A B C D
// 3. A B D

 

JavaScript

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

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

const  initialize = () => {
    let  ptr;
    head = new  Node('H');
    end = new  Node('E');

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

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

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

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

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

    indexPtr.next.prev = indexPtr.prev;
    indexPtr.prev.next = indexPtr.next;
}

const  main = () => {
    let  ptr;
    let  ret = "";
    let  i = 0;

    initialize();
    ptr = head.next;

    for(i=0; i<3; i++) {
        ret += ` ${ptr.data}`;
        ptr = ptr.next;
    }
    console.log(ret);

    ret = "";
    temp = new  Node('C');
    insertNode(temp);
    ptr = head.next;
    for(i=0; i<4; i++) {
        ret += ` ${ptr.data}`;
        ptr = ptr.next;
    }
    console.log(ret);

    ret = "";
    deleteNode(temp);
    ptr = head.next;
    for(i=0; i<3; i++) {
        ret += ` ${ptr.data}`;
        ptr = ptr.next;
    }
    console.log(ret);
}

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