[study] Linked List (연결 리스트)

 

Linked List 란?

- 연결리스트 라고도 부른다.

- 배열이 순차적으로 연결된 공간에 데이터를 나열한다면, Linked List는 떨어진 곳에 존재하는 데이터를

 화살표로 연결해서 나열하고 관리하는 데이터 구조이다.

- 추상적 자료형인 '리스트' 를 구현한 자료구조이다.

 

기본적인 구성은

데이터 덩어리 (노드) 를 저장할 때, 다음 순서의 자료가 있는 위치를

데이터에 포함시키는 방식으로 자료를 저장. 자료를 엮어둔 개념이다.

 

예시)

배열 : 사과 1번, 배 2번, 딸기 3번 ... (자료에 순번이 정해져 있음.)

Linked List : 사과 다음 배, 배 다음 딸기, 딸기 다음 ... (자료에 다음 자료를 연결한다.)

 

배열은 특정 자료를 불러내기 용이한 면이 있고, Linked List는 노드를 추가로 연결하거나, 중간에 끼워 넣는게 용이.

따라서, 탐색 또는 정렬을 자주 하면 '배열', 추가나 삭제가 많으면 'Linked List'가 유리하다.

 

Linked List 구현 방법1 (노드 생성 - 구조체)

 

일반적으로 구조체와 포인터로 구성된다. 연결 및 참조 방식에 따라 단순 연결 리스트, 이중 연결 리스트,

순환 연결 리스트, 청크 리스트 등으로 나뉜다. 이 게시물에서는 단순 연결 리스트로만 다룸.

 

struct s_list
{
	void		*content;
	struct s_list	*next;
}			t_list;

 

우선 구조체를 활용하여 정의한다.

이러한 구조체 인스턴스 하나는 연결리스트 데이터 하나의 노드와 대응되어지고,

데이터 등을 content로 넣고 (이 때 자료형은 어떤 자료형이든 넣을 수 있고, 지금은 void 포인터로 어떤 데이터든

받을 수 있도록 해둠) next 라는 이름의 다음 노드 위치를 표시해주는 포인터를 포함 시켜준다.

해당 포인터는 노드의 포인터, 즉 구조체 포인터로 만들어지므로 struct s_list 를 붙혀준다.

(next 말고 같은 방식으로 previous를 만든 뒤 해당 포인터는 이전 노드를 가르켜준다면 이중 연결 리스트가 된다.)

 

Linked List 구현 방법2 (포인터 - head, tail)

 

노드를 의미하는 구조체를 만들었다면, 노드들을 가리키는 포인터들에 대해서 알아보겠다.

우선 head 이다. 이 head는 리스트에서 가장 첫번째 노드를 가리킬 포인터이다.

반대로 tail은 가장 마지막 노드를 가리킬 포인터가 된다.

 

1. 가장 앞에 노드를 삽입하는 경우

- 연결 리스트가 비어있으면 (head 가 NULL인 경우) ,  newnode를 생성하고, head가 newnode를 가리키게 한다.

- 연결 리스트가 비어있지 않은 경우, newnode를 생성하고, head가 가리키는 노드를 newnode의 next 가 가리키게 한다.

  그리고 head가 newnode를 가리키게 한다.

=> 비어있지 않으면 newnode는 기존에 있던 노드 앞으로 가야하므로 next에 그 기존 노드 위치를 넣어주는 것인데,

그 기존 노드 위치는 head가 원래 가리키고 있었기에 head가 가리키는 그 포인터를 newnode의 next로 대응시킨다.

 

2. 가장 뒤에 노드를 삽입하는 경우

- newnode를 만들고, 마지막 노드의 next 포인터가 newnode를 가리키게 하면 된다.

 

3. 중간에 노드를 삽입하는 경우

- newnode를 생성하고, newnode의 next 포인터가 이전 노드의 next가 가리키는 노드를 가리키게 한다.

(철수 -> 영희 였으면, 철수 -> 영희, newnode -> 영희 상태가 된다.)

- 이후 이전 노드의 next는 newnode를 가리키도록 만들어주면 된다.

(철수 -> 영희, newnode -> 영희 였으면, 철수 -> newnode -> 영희 상태가 된다.)

 

Linked List 삭제 방법

 

1. 가장 앞의 노드를 삭제하는 경우

- cur 라는 포인터를 만들고, 해당 cur가 지울 노드를 가리키게 한다.

그리고, head 가 cur -> next 를 가리키게 하면, head는 기존 cur의 다음 노드를 가리키게 된다.

그 다음 cur -> next 를 NULL로 설정하면 리스트에서 벗어난 노드가 되고, 이 cur를 free 시키면 완료된다.

 

2. 가장 뒤 또는 중간의 노드를 삭제하는 경우

- prev와 cur 포인터를 만들고, prev는 삭제할 노드의 이전 노드를 가리키게 할 것이다.

우선, prev 포인터와 cur 포인터 모두 head가 가리키는 첫번째 노드를 가리키게 한다.

그 후, cur 포인터는 다음 노드를 가리키게 하여, 삭제를 원하는 데이터가 cur -> data와 일치할 때까지 다음 노드로 넘어간다.

cur -> data가 삭제할 데이터가 맞으면, 삭제 과정을 진행한다.

prev -> next는 cur -> next가 되면 cur 부분을 건너뛰고, cur -> next는 NULL을 가리키게 하여 리스트에서 벗어나도록 한다.

그 다음 cur를 free 시키면 삭제 과정이 마무리 된다.

 

Linked List 탐색 방법

 

반복문을 통해 head 부터 쭉 포인터를 next로 옮겨가게 하면서 원하는 data를 발견할 때까지 반복한다.

발견하면 return 1, 미발견하면 return -1 하는 등의 동작을 수행하게 만들 수 있다.

 

배열과의 비교

크기 : 배열은 고정적이고, Linked List는 동적이다.

주소 : 배열은 순차적이고, Linked List는 랜덤이다. (논리적 저장순서와 물리적 저장순서가 배열은 일치, 연결리스트는 다름)

접근 속도 : 배열은 O(1), Linked List는 O(n) (배열은 인덱스로 바로 접근, 연결리스트는 순차적으로 탐색해야함.)

삽입/삭제 속도 : 배열은 O(n), Linked List는 O(1) (배열은 기존 데이터 위치 변경. 연결리스트는 포인터 설정만 변경)