[DevLog][DS] Linked List 연결 리스트

리스트 구현 방식

Sequantial List 순차 리스트 = array

고정된 크기의 배열. 연속적으로 구현되어 있어 순차적/임의 접근이 가능하다. 따라서 순차적으로 요소를 삽입하거나 탐색하는 데는 용이하지만 중간 요소의 삽입/삭제/수정이 어렵다. 또 고정된 크기로 존재하여 가변 크기의 배열을 저장할 경우 공간 낭비가 될 수 있다.

Linked List 연결 리스트

Link로 연결된 가변 크기의 배열. 데이터와 다음 요소를 가리키는 포인터(=link) 를 포함하고 있는 자기참조 구조체로 구현한다. 요소의 삽입/삭제/수정이 용이하고 가변크기의 배열을 저장하는 데 효율적이다. 반면 인덱스를 통한 임의접근이 어려워 탐색에 비효율적일 수 있다.

Linked List 개념

• Linked List의 각 요소는 data값과 다음 요소를 가리키는 포인터를 갖는다.
• 마지막 요소의 포인터는 NULL 이다.
• Linked List의 각 요소는 메모리에 비연속적/임의적 순서로 저장된다.
• 즉, 논리적 순서와 물리적 순서가 무관하다

Functions

• Create

  • 임의 data 와 자기 자신 포인터 변수 *link를 member로 갖는 구조체를 선언한다.

• Insert

  • newNode를 만든다.
  • insert 하고자 하는 위치의 직전 요소를 찾는다.
  • newNode의 링크에 직전 요소의 링크값을 복사한다.
  • 직전 요소는 newNode와 링크한다.

• Delete

  • delete하고자 하는 요소의 직전 요소를 찾는다.
  • 직전 요소의 link를 delete하고자 하는 요소의 다음 요소 주소값으로 수정한다.
  • delete하고자 하는 요소의 메모리 할당 해제

Linked List의 종류

1. Singly Linked List
2. Singly Circular Linked List
3. Doubly Linked List
4. Doubly Circular Linked List

Singly Linked List 구현하기

typedef struct _SLL {
  char data;
  struct _SLL *link;
} SLL;

SLL *first;
SLL *second;
SLL *lastElem;

first->data    = 0;
second->data   = 1;
lastElem->data = 2;

first->link    = second;
second->link   = lastElem;
lastElem->link = NULL;

//pointer variable to read data
SLL *currElem;

//print the first data
currElem = first;
printf("%c", currElem->data);

//print the second data
currElem->second;
printf("%c", currElem->data);

// Insert
//inserting an elem at the front of the list
struct listNode *newNode;
newNode = malloc(sizeof(*newNode)); //새 메모리 할당
newNode->data = sth;  //임의의 데이터
newNode->link = NULL;
newNode->link = first; //첫 번째 노드를 가리키는 주소 => update!
first = newNode; //첫 번째 노드 변수를 새로운 변수로 update

//inserting an elem int the middle of the list
struct listNode *newNode;
newNode = malloc(sizeof(*newNode)); //새 메모리 할당
newNode->data = sth;  //임의의 데이터

beforeNode = sth; //삽입하고자 하는 위치의 직전 노드
newNode->link = beforeNode->link; //newNode의 링크는 beforeNode link
beforeNode->link = newNode; //직전 노드는 newNode와 링크

// Delete

SLL *deleteElem;

//delete an element from the middle of the list
//delete the second element
SLL *beforeElem;
beforeElem = first;
deleteElem = beforeElem->link;
beforeElem->link = beforeElem->link->link;
free(deleteElem);

첫 번째 요소를 삭제하려면 first = first->link만 하면 된다.

Note: Memory Pool

이와 같은 방식으로 Singly Linked List를 구현하면 element를 삽입/삭제/수정할 때 마다 메모리를 할당-해제하게 된다. malloc()과 free()함수는 시간 면에서 효율적인 함수가 아니기 때문에, 큰 규모의 연결리스트를 동적으로 운영하기에는 시간적인 부담이 크다. (정적할당 방식이 한번에 메모리를 할당받고 해제하는 것과 달리) 따라서 storage pool이라는 별도 연결리스트를 이용해 효율적으로 관리할 필요성이 생긴다. 시스템 메모리로부터 한번에 일정 메모리를 할당받아 두고, 프로그램에서 SLL을 할당/해제할 때마다 allocSLL(), freeSLL() 함수를 이용해 동적으로 노드를 연결한다. 즉, storage pool을 이용한 Singly Linked List Management는 순차 리스트와 연결 리스트의 장점을 결합한 방식이라고 볼 수 있다.