[C언어로 쉽게 풀어쓴 자료구조] 6장 연결 리스트

리스트 

• 객체 : n개의 element형으로 구성된 순서 있는 모임
• 연산 : 
  • insert(list, pos, item) : pos 위치에 요소를 추가
  • insert_last(list, item) : 맨 끝에 요소를 추가
  • insert_first(list, item) : 맨 처음에 요소를 추가
  • delete(list, pos) : pos 위치의 요소를 제거
  • clear(list) : list의 모든 요소를 제거
  • get_entry(list, pos) : pos위치의 요소를 반환
  • get_length(list) : list의 길이를 구함
  • is_empty(list) : list가 비었는지 검사
  • is_full(list) : list가 꽉찼는지를 검사
  • print_list : list의 모든 요소를 표시

 

리스트의 구현

• 배열
  • 구현이 간단하고 속도가 빠름
  • but, 크기가 고정 ( 동적으로 크기를 늘리거나 줄이는 것이 힘듦)
• 연결리스트
  • 크기가 제한되지 않고, 중간에서 쉽게 삽입하거나 삭제할 수 있는 유연한 리스트를 구현 가능
  • 구현이 복잡하고 임의의 항목(i번째 항목)을 추출하려고 할때는 배열을 사용하는 방법보다 시간이 많이 걸림

 

배열로 구현한 리스트

length : size와 같은 의미

length가 0 이면 공백 / MAX size라면 포화 상태

삽입 연산 

• 삽입위치 다음의 항목들을 이동
• 해당위치에 value를 넣으려면 해당 위치부터 max까지 들어간 요소를 한칸씩 뒤로 옮겨줘야함. 그리고 length를 올려줘야함(배열의 크기를 제대로 알기 위함)

// 삽입 연산
void insert(int pos, int e){
    if(!isFull() && pos >=0 && pos <= length){
        for (int i = length; i > pos; i--)
            data[i] = data[i-1];
        data[pos] = e;
        length++;
    }
    else error("포화 상태 또는 삽입 위치 오류");
}

삭제 연산 

• 삭제위치 다음의 항목들을 이동
• 빼내고 싶은 value의 위치 다음부터 max까지 들어간 요소를 한칸씩 앞으로 옮겨줘야한다. 그리고 length를 내려줘야지 제대로 된 배열을 구현할 수 있음 

//  삭제 연산
void remove(int pos){
    if(!isEmpty() && pos <= length){
        for (int i = pos +1; i <length; i ++)
            data[i-1]=data[i];
        length--;
    }
    else error("공백 상태 또는 삭제 위치 오류");
}

 

 

연결리스트로 구현한 리스트

• 단순 연결 리스트
• 원형 연결 리스트
  • : head를 맨앞이 아니라 맨 뒤로 해서 앞으로 이어주게 된 경우
• 이중 연결 리스트
  • : 링크 필드가 원래 next의 link로 하나만 가리켰는데, prev의 Link까지 가리키게 되어서 쌍방향 소통이 될 수 있도록 함

삽입 연산 

• 삽입연산은 새로 들어온 노드의 링크에 그 전의 링크를 넣어주고, 그전의 링크에다가는 들어온 노드를 넣어줌

삭제 연산 

• 빼내고 싶은 노드 전의 링크에 빼내고 싶은 노드의 링크를 넣어주고, 빼내고 싶은 노드를 삭제
•  

// 삽입 연산
void inserNext(Node* n){
    if(n != NULL){
        n->link = link;
        link = n;
    }
}

// 삭제 연산
    Node* removeNext(){
        Node* removed = link;
        if(removed != NULL)
            link = removed->link;
        return removed;
    }

// pos번째 항목을 반환함

Node* getEntry(int pos){

Node* n = &org;

for(int i = -1; i<pos; i++, n=n->getLink())

if(n==NULL) break;

return n;

}

// 리스트의 어떤 위치에 항목 삽입

void insert(int pos, Node *n){

Node* prev = getEntry(pos-1);

if(prev != NULL)

prev-> insertNext(n);

}

// 리스트의 어떤 위치의 항목 삭제

Node* remove(int pos){

Node* prev = getEntry(pos-1);

return prev -> removeNext();

}

이중연결리스트 삽입 / 삭제 연산 

• 노드 구조의 변경

Struct Node2{

Element data;

Node2 * prev;

Node2 * next;

};

• 이중 연결 리스트의 구조
  • p==p->next->prev==->prev->next
  • 해당노드의 뒤의 앞이며, 해당 노드의 앞의 뒤이다.
  •  

// 이중연결리스트

// 자신의 다음에 새로운 노드 n을 삽입하는 함수
void insertNext(Node2 *n){
    if(n!= NULL){
        n->prev=this;
        if(next != NULL) next->preb = n;
        next = n;
    }
}

// 현재 노드를 연결 리스트에서 제거하는 함수
Node2* remove(){
    if(prev != NULL) prev-> next = next;
    if(next != NULL) next->prev = prev;
}