자료구조 연결리스트

리스트의 개념

의미

일정한 순서의 나열

어떤 정의에 의해서 결정된 논리적인 순서의 나열

리스트의 순서는 데이터가 저장되는 물리적인 위치와 상관없이 사람들의 머리속에 인식되는 논리적인 순서 혹은 리스트에 나타나는 원소들 간의 의미적인 순서를 의미함

 

배열은 인덱스로 표현되는 추상적 순서가 배열 원소의 메모리 공간에서의 물리적인 위치와 일치함 하지만 리스트의 순서 개념은 어떤 정의에 의해서 결정된 논리적인 순서 

원소들의 물리적인 저장 순서나 위치와는 무관하게 원소들 간의 논리적인 순서만 유지

 

정의

원소의 메모리 공간의 물리적인 위치를 순서적으로 결정하는 특징

배열의 순서는 메모리 공간에서 저장되는 원소값의 물리적 순서

 

배열을 이용한 리스트의 구현

 

포인터를 이용한 리스트의 구현

노드의 구조

노드 = 리스트의 원소값 + 다음 원소를 가리키는 정보

 

포인터 변수

 

연결 리스트의 삽입과 삭제

리스트의 원소 삭제 연산 단계

삭제할 노드의 선행 노드의 링크 필드를 삭제할 노드의 후행 노드를 가리키게 한다. 

삭제할 노드의 메모리 반환 

 

리스트의 원소 삽입 연산 단계

메모리 공간을 할당받고 삽입할 내용을 저장하여 삽입할 x노드를 생성

x 노드의 링크부분이 후행 노드가될 j노드를 가르키게 한다.

삽입된 x노드의 선행 노드가 될 i노드의 링크 필드가 x 노드를 가르키게 한다.

 

연결 리스트의 여러가지 연산

 

 

1. 리스트의 ‘순서’는 데이터가 저장되는 물리적인 위치와 상관없이 사람들의 머릿속에 인식되는 ‘논리적인 순서’, 혹은 리스트에 나타나는 원소들 간의 ‘의미적인 순서’를 의미합니다.
2. 배열을 이용한 리스트의 구현은 실제 IT 서비스 환경에서는 자주 사용되지 않고 있습니다. 자료의 삽입과 삭제가 빈번히 발생하는 상황에서, 리스트를 배열로 구현하는 것은 빈번한 자료 이동으로 인한 비효율적인 컴퓨팅 성능을 유발합니다.
3. 포인터를 이용하는 방법은 원소의 자리에는 원소값을 저장하고, 다음 원소를 가리키는 정보의 자리에는 다음 원소가 저장될 위치의 주소값을 저장합니다. 조금 더 ‘프로그램’스럽게 설명하자면, 리스트의 원소 자리와 다음 원소를 가리키는 정보의 자리를 합쳐서 노드(node)라고 합시다. 노드에는 데이터 요소(원소)와 리스트의 다음 원소를 지시하는 포인터(pointer, 주소)를 가진다고 생각하면 됩니다. 이 포인터는 링크(link)라고도 부릅니다.
4. 포인터의 ‘메모리 주소값’이라는 것은 메모리에 저장되는 값의 위치라고 생각하면 됩니다. 메모리에 저장되는 값(데이터)은 저장 위치에 대한 주소를 가지며, 이 저장 위치를 이용해서 리스트의 원소값을 찾아갈 수 있습니다.
5. 다양한 데이터형의 변수를 하나의 상자 안에 넣어서 선언하거나 사용하는 C 프로그래밍 문법이 구조체(struct)입니다.

 

연결리스트의 변형

단순연결, 이중연결, 단순 원형 연결, 이중 원형 연결 리스트

 

단순연결 리스트의 문제점 

하나의 링크만 있고 각가의 노드의 링크는 후행 노드만을 가리키는 구조

 

이중연결리스트

선행 노드를 가리키는 링크와 후행 노드를 가리키는 링크를 가짐

특정 노드에서 선행 노드와 후행 노드의 직접적으로(간단한 프로그램 코드를 통해)접근할 수 있음

 

원형 연결 리스트

연결 리스트를 보면 가장 마지막 노드의 링크 필드는 언제나null 값이다

리스트의 마지막 원소 뒤에는 아무 원소도 없기 때문에 연결 리스트의 마지막 노드 링크 필드는 언제나 null값

그래서 마지막 노드의 링크 필드를 활용하면서도 프로그램 성능에 도움이 되도록 하기 위해서 원형 연결 리스트 제안됨

 

원형 연결 리스트

연결리스트의 마자막 노드의 링크 필드를 활용하면서도 프로그램 성능에 도움이 되도록 하기 위해서 원형 연결 리스트

 

typedef struct ListNode { // 원형 연결 리스트의 노드 구조 정의

    int data,

    struct ListNode* link;

} listNode;

 

typedef struct{ // 원형 연결 리스트의 헤드 노드 구조 정의

    listNode* head;

} linkedList h;

 

linkedList_h* createLinkedList_h(void) {

    linkedList_h* H;

    H = (linkedList_h*)malloc(sizeof(linkedList_h));

    H -> head = NULL;

    return H;

}

 

이중연결 리스트

단순 연결 리스트의 단점

어떤 노드를 찾은 경우, 그 특정 녿의 후행 노드는 쉽게 찾을 수 있었지만, 어떤 특정 노드의 선행 노드를 찾으려면 복잡한 방법이 필요함

 

구조

양쪽 방향으로 순회할 수 있도록 링크 필드 두 개 필요

시작점(head)도 두개 링크 필요 (Lhead, Fhead) 필요

이중연결 리스트의 노드 구조 = 두 개의 링크필드(Llink, Rlink)와 한개의 데이터 필드

 

typedef struct ListNode { // 이중 연결 리스트의 노드 구조 정의

    struct ListNode* Llink;

    int data,

    struct ListNode* Rlink;

} listNode;

 

typedef struct{ // 이중 연결 리스트의 헤드 노드 구조 정의

    listNode* Lhead;

    listNode* Fhead;

} linkedList h;

 

linkedList_h* createLinkedList_h(void) {

    linkedList_h* H;

    H = (linkedList_h*)malloc(sizeof(linkedList_h));

    H -> Lhead = NULL;

    H -> Fhead = NULL;

    return H;

}

 

단순 연결 리스트 = 링크부분이 하나만 있고, 각각의 노드는 후행 노드만을 가르키는 구조

이중 연결 리스트 = 특정 노드에서는 선행 노드와 후행 노드에 대해 간단한 프로그램 코드를 통해 접근할 수 있는 구조

원형 연결 리스트 = null값을 가즌ㄴ 마지막 노드의 링크 부분을 활용하면서도 프로그램 성능에 도움을 주기 위해 제안 되었으며 한 방향으로 모든 노드가 원형으로 계속 연결되어 있기 때문에 한 노드로부터 어떤 노드로도 접근이 가능 한 구조