[06]C언어 연결리스트 :: 이중연결리스트/이중연결리스트설명/이중연결리스트 초기화/삽입

요 앞전에는 단일연결리스트를 알아봤는데요 

↓↓

2019/02/08 - [IT&컴퓨터공학/자료구조&알고리즘] - [04]C언어 연결리스트 :: 단일리스트 초기화/삽입

2019/02/12 - [IT&컴퓨터공학/자료구조&알고리즘] - [05]C언어 연결리스트 :: 단일연결리스트 데이터 탐색/삭제/출력

이번에 알아볼 리스트는 바로 " 이중연결 리스트 " 입니다.  양방향연결리스트 라고 불리기도 해요 !!

앞에서 봤던 단일연결리스트에서는,

왼쪽노드가 오른쪽 노드만을 가르키기 때문에, 20에서 30으로 가는 방법이 없어요 !

그래서 예를들어 20 왼쪽에 있는 노드를 삭제해라 ! 라고 하면

20을 찾는 노드 cur 만으로 해결할 수 없고

20의 왼쪽에 있는 노드를 가르킬 before 노드가 하나 더 필요했습니다.

이 단점을 보완한게 바로 이중연결리스트 인데요.

이중연결리스트의 노드는

요렇게 생겼습니다 !

단일연결리스트에서 봤던 노드에 " prev : 왼쪽의 노드를 가르키는 포인터 " 가 추가됐네요.

그렇다면 이중연결리스트의 모습은

이렇게 그릴 수 있겠네요 !

이제 이중연결리스트의 구현 코드들을 살펴보겠습니다.

• 리스트 구조체 & 노드 구조체 

typedef struct _Node {
    int data;
    struct _Node *prev; // 추가된 부분
    struct _Node *next;
}Node;
 
typedef struct _List {
    Node *head;
    int numofData;
}List;

추가된 부분빼고 단일리스트랑 똑같네요 !

• 리스트 초기화 & 노드 만드는 함수(getNode)

Node *getNode()
{
    Node *new = (Node*)malloc(sizeof(Node));
    new->prev = NULL; // 추가된 부분
    new->next = NULL;
    return new;
}
 
List *initList()
{
    List *L = (List*)malloc(sizeof(List));
    L->head = NULL;
    L->numofData = 0;
    return L;
}

이 역시 한줄만 더 추가하면 되겠네요 !   

혹시 위 코드들이 이해가 안되면 단일연결리스트 포스팅을 보시면 자세하게 나와있습니다 : )

자 이제 노드의 삽입을 살펴볼까요 ? 삽입부터는 단일리스트와 코드가 조금 달라져요 !

• 노드의 삽입

삽입은 단일연결리스트에서 봤던것처럼

⑴ 리스트 안에 아무것도 없을 때 삽입하는 경우

⑵ 리스트 안에 이미 어떤 노드가 있을 때 삽입하는 경우

이렇게 두가지 경우로 볼 수 있습니다 !

⑴ 첫번째 경우를 그림으로 나타내보면

단일연결리스트랑 다를게 없죠 ?

과정을 말로 풀어써보자면,

① newNode->next 는 NULL

② 리스트의 head 는 newNode를 가르키도록

⑵ 다소 복잡한건 두번째 경우인데요 ! 두번쨰 경우를 그림으로 나타내자면

이렇게 나타낼 수 있겠네요 !

여기서 주의할점은 1번 2번 과정은 서로 순서가 바뀌어도 괜찮지만, 3번만큼은 항상 마지막에 해줘야 한다는 점입니다 !!!

3번 과정을 처음에 해버리면, 

10하고 연결되는 노드가 하나도 없어서 10을 표현할 수가 없기 때문입니당 !!

이제 이과정을 코드로 나타내볼까요 ?

void Insert(List *L, int number)
{
    Node *newNode = getNode();
    newNode->data = number;
 
    if (L->head == NULL) //리스트가 비어있을때
    {
        L->head = newNode;
        newNode->next = NULL;
    }
    
    else // 리스트에 하나의 노드라도 존재할때
    {
        L->head->prev = newNode; // 1번과정
        newNode->next = L->head; // 2번과정
        L->head = newNode; // 3번과정
    }
}

 

코드길이로 보면 한줄만 더 추가됐네요 : )