c언어 double linked list 구현

흠.. 일단 그냥 막 내가 쓰고 싶은 대로 구현하긴 했다.

 

prev, next를 통해서 전과 후로 갈 수 있고

 

insert,delete가 O(1)에 해결 가능하다.

 

insert는 여러 버전이 있는데, index에 추가하는 것과, 가리키고 있는 node에 insert하는 것과, 제일 앞에 insert, 그리고 제일 뒤에 insert을 넣는 버전이 있다.

 

#include <stdlib.h>
typedef long long ll;
typedef struct node{
    char value;//값
    struct node* prev;//전
    struct node* next;//다음
}node;

typedef struct Linkedlist{
    node* front;//맨 앞
    node* back;//맨 뒤
    ll size;//크기
}Linkedlist;

void idxinsert(Linkedlist* arr,int idx,char v){//어느 위치에 넣어라. (인덱스 위치에)
    node* find=arr->front;
    for(int i=0;i<idx;i++)find=find->next;//idx만큼 간다.
    node* newinsert=(node *)malloc(sizeof(node));
    newinsert->value=v;
    newinsert->prev = find->prev;//이전 값 갖고 오기
    newinsert->next = find;//find가 다음 값이 되기.
    newinsert->prev->next = newinsert;//전에 값의 다음이 newinsert가 돼야함.
    
    find->prev = newinsert;//find의 이전이 newinsert가 돼야 한다.
    arr->size++;//사이즈 키우기.
}
void insert(Linkedlist* arr,char v){//앞으로 넣기
    node* newinsert=(node *)malloc(sizeof(node));
    newinsert->value = v;
    newinsert->prev=NULL;//이전은 없다.
    if(arr->size){//이미 값을 넣은 적이 있었다.
        newinsert->next = arr->front;
        arr->front->prev = newinsert;
        arr->front = newinsert;
    }else{//없었음
        newinsert->next=NULL;
        arr->front=newinsert;
        arr->back=newinsert;
    }
    arr->size++;
}
void insertback(Linkedlist*arr,char v){//맨 뒤에 삭제
    node* newinsert=(node *)malloc(sizeof(node));
    newinsert->value = v;
    newinsert->next=NULL;
    if(arr->size){
        newinsert->prev=arr->back;
        arr->back->next = newinsert;
        arr->back = newinsert;
    }else{
        newinsert->prev=NULL;
        arr->back=newinsert;
        arr->front=newinsert;
    }
    arr->size++;
}
void myinsert(Linkedlist*arr,node*my,char v){//해당하는 node의 곳에 insert
    node* newinsert=(node *)malloc(sizeof(node));
    newinsert->value = v;
    if(arr->front == my){
        insert(arr,v);//abcdx
    }else{//abcdxy
        newinsert->prev =my->prev;
        newinsert->next =my;
        my->prev = newinsert;
        newinsert->prev->next = newinsert;
        arr->size++;
    }
}
void init(Linkedlist* arr){
    arr->size=0;
    arr->front=NULL;
    arr->back=NULL;
}
void mydelete(Linkedlist* arr,node* my){
    node* point = my->prev;
    if(point == arr->front){
        arr->front=my;
    }else{
        point->prev->next = my;//이전의 이전의 다음값이 my라고 바로 보내기.
        my->prev = point->prev;
    }
    free(point);//날리기
    arr->size--;
}

이번 구현은 그냥 진짜 내가 필요하다고 느끼는 함수들만 만들어 놓은 것이므로 나중에 충분히 수정 보안할 수 있다.