알고리즘 스터디 1회차 - 연결리스트(Linked List) 구현

동아리에서 진행하는 알고리즘 스터디 1회차 과제는 연결 리스트(Linked List) 구현하기이다. 단방향 연결 리스트(Single Linked List), 복합 연결 리스트(Double Linked List), 원 연결 리스트(Circular Linked List)를 구현하는 것이었는데 시간 관계상 단방향과 복합 연결 리스트까지만 만들었다. 기능은 insert, delete, print 세 가지이고, 예외 처리를 거의 안해서 구멍이 송송 뚫려 있는 코드이니... 개념을 다졌다는데에만 의의를 두고 싶다. 아래는 코드 전문이다.

1. 단방향 연결 리스트 (Single Linked List)

#include <stdio.h>
#include <stdlib.h>
 
typedef struct singleLinkedList {
    struct node *head;
    struct node *tail;
}singleLinkedList;
 
typedef struct node {
    int key;
    struct node *next;
}node;
 
void insert(singleLinkedList *list, int keyData) {
    node *newNode = (node *)malloc(sizeof(node));
    newNode->key = keyData;
    newNode->next = NULL;
    if (list->head == NULL && list->tail == NULL) {
        list->head = newNode;
        list->tail = newNode;
    }
    else {
        list->tail->next = newNode;
        list->tail = newNode;
    }
}
 
void Delete(singleLinkedList *list, int keyData) {
    node *prevNode = list->head;
    if (prevNode->key == keyData) {
        prevNode->next = list->head;
    }
    else {
        while (1) {
            if (prevNode->next->key == keyData) {
                if (prevNode->next->next == NULL) {
                    list->tail = prevNode;
                    break;
                }
                prevNode->next = prevNode->next->next;
                break;
            }
            prevNode = prevNode->next;
        }
    }
}
 
void print(singleLinkedList *list) {
    node *currentNode = list->head;
    while (1) {
        printf("%d\n", currentNode->key);
        if (currentNode == list->tail) break;
        currentNode = currentNode->next;
    }
}
 
int main(void) {
    int com, key;
    singleLinkedList *list = (singleLinkedList *)malloc(sizeof(singleLinkedList));
    list->head = NULL;
    list->tail = NULL;
    while (1) {
        printf("\nsingleLinkedList :: 1-insert, 2-delete, 3-print\n");
        scanf_s("%d", &com);
 
        switch (com) {
        case 1:
            scanf_s("%d", &key);
            insert(list, key);
            break;
        case 2:
            scanf_s("%d", &key);
            Delete(list, key);
            break;
        case 3:
            print(list);
            break;
        }
    }
}

2. 복합 연결 리스트 (Double Linked List)

#include <stdio.h>
#include <stdlib.h>
 
typedef struct doubleLinkedList {
    struct node *head;
    struct node *tail;
}doulbeLinkedList;
 
typedef struct node {
    int key;
    struct node *next;
    struct node *prev;
}node;
 
void insert(doubleLinkedList *list, int keyData) {
    node *newNode = (node *)malloc(sizeof(node));
    newNode->key = keyData;
    newNode->next = NULL;
    newNode->prev = NULL;
 
    if (list->head == NULL && list->tail == NULL) {
        list->head = newNode;
        list->tail = newNode;
    }
    else {
        list->tail->next = newNode;
        newNode->prev = list->tail;
        list->tail = newNode;
    }
}
 
void Delete(doubleLinkedList *list, int keyData) {
    node *prevNode = list->head;
    if (prevNode->key == keyData) {
        prevNode->next = list->head;
    }
    else {
        while (1) {
            if (prevNode->next->key == keyData) {
                if (prevNode->next->next == NULL) {
                    list->tail = prevNode;
                    break;
                }
                prevNode->next = prevNode->next->next;
                prevNode->next->prev = prevNode;
                break;
            }
            prevNode = prevNode->next;
        }
    }
}
 
void print(doubleLinkedList *list) {
    node *currentNode = list->head;
    while (1) {
        printf("%d\n", currentNode->key);
        if (currentNode == list->tail) break;
        currentNode = currentNode->next;
    }
}
 
int main(void) {
    int com, key;
    doubleLinkedList *list = (doubleLinkedList *)malloc(sizeof(doubleLinkedList));
    list->head = NULL;
    list->tail = NULL;
    while (1) {
        printf("\ndoubleLinkedList :: 1-insert, 2-delete, 3-print\n");
        scanf_s("%d", &com);
 
        switch (com) {
        case 1:
            scanf_s("%d", &key);
            insert(list, key);
            break;
        case 2:
            scanf_s("%d", &key);
            Delete(list, key);
            break;
        case 3:
            print(list);
            break;
        }
    }
}

c로 구현하다보니 코드가 너무 길다... 파이썬이었다면 편했을텐데...

... 그래서 파이썬으로 해봤다.

1. 단방향 연결 리스트

>> slist.py

class SList:
    class Node:
        def __init__(self, item, link):
            self.item = item
            self.next = link
 
    def __init__(self):
        self.head = None
        self.size = 0
 
    def size(self): return self.size
    def is_empty(self): return self.size == 0
 
    def insert_front(self, item):
        if self.is_empty():
            self.head = self.Node(item, None)
        else:
            self.head = self.Node(item, self.head)
        self.size += 1
 
    def insert_after(self, item, p):
        p.next = SList.Node(item, p.next)
        self.size += 1
 
    def delete_front(self):
        if self.is_empty():
            raise EmptyError('Underflow')
        else:
            self.head = self.head.next
            self.size -= 1
 
    def delete_after(self, p):
        if self.is_empty():
            raise EmptyError('Underflow')
        t = p.next
        p.next = t.next
        self.size -= 1
 
    def search(self, target):
        p = self.head
        for k in range(self.size):
            if target == p.item: return k
            p = p.next
        return None
 
    def print_list(self):
        p = self.head
        while p:
            if p.next != None:
                print(p.item, ' -> ', end='')
            else:
                print(p.item)
            p = p.next
 
class EmptyError(Exception):
    pass

>> main.py

from slist import SList
if __name__ == '__main__':
    s = SList()
    print('단방향 연결 리스트 with Python')
    s.insert_front('apple')
    s.insert_front('banana')
    s.insert_after('pear', s.head.next)
    s.print_list()
    s.delete_front()
    s.print_list()

2. 복합 연결 리스트

>> dlist.py

class DList:
    class Node:
        def __init__(self, item, prev, link):
            self.item = item
            self.prev = prev
            self.next = link
 
    def __init__(self):
        self.head = self.Node(None, None, None)
        self.tail = self.Node(None, self.head, None)
        self.head.next = self.tail
        self.size = 0
 
    def size(self): return self.size
    def is_empty(self): return self.size == 0
 
    def insert_before(self, p, item):
        t = p.prev
        n = self.Node(item, t, p)
        p.prev = n
        t.next = n
        self.size += 1
 
    def insert_after(self, p, item):
        t = p.next
        n = self.Node(item, p, t)
        t.prev = n
        p.next = n
        self.size += 1
 
    def delete(self, x):
        f = x.prev
        r = x.next
        f.next = r
        r.prev = f
        self.size -= 1
        return x.item
 
    def print_list(self):
       if self.is_empty():
           print('리스트 비어있음')
       else:
           p = self.head.next
           while p != self.tail:
               if p.next != self.tail:
                   print(p.item, ' <=> ', end='')
               else:
                   print(p.item)
               p = p.next
 
class EmptyError(Exception):
    pass

>> main.py

from dlist import DList
if __name__ == '__main__':
    s = DList()
    print('양방향 연결 리스트 with Python')
    s.insert_after(s.head, 'apple')
    s.insert_before(s.tail, 'banana')
    s.insert_after(s.head.next, 'pear')
    s.print_list()
    s.delete(s.tail.prev)
    s.print_list()

비슷해 보이긴 하는데 파이썬이 훨씬 편안하다.