Linked List

연속적인 데이터를 표현하는 방법에는 여러가지 방법이 있을 수 있다. 배열이 있을 수도 있고, 어레이 리스트, 벡터, 링크드 리스트 등이 있다. 이번엔 링크드 리스트(연결 리스트)에 대해 알아보겠다.

개념

• 연결 리스트는 배열과 같이 여러 데이터를 연속적으로 나타내는 데이터 구조 중 하나이다.
• 데이터를 담는 노드들로 구성이 된다.
• 노드는 데이터를 저장하는 데이터 필드와 다음 노드의 주소를 가리키는 링크 필드로 구성된다.
• 노드의 종류는 리스트의 시작인 헤드 노드(Head Node)와 리스트의 끝인 테일 노드(Tail Node), 그 외의 노드가 있다.
• 헤드 노드는 구현에 따라 데이터 필드가 있을 수도 있고 없을 수도 있다.
• 테일 노드는 다음 노드를 가리키는 링크의 값이 NULL이다. (NULL을 가리킨다.)

특징 (연결 리스트 vs 배열)

• 배열이라는 데이터 구조가 있는데 왜 굳이 연결 리스트를 만들어서 쓸까?
• 가변길이 : 필요에 따른 동적인 할당이 가능하다. 배열은 컴파일 타임 전에 크기가 미리 정해져 있지만 연결 리스트는 필요에 따라 추가하고 삭제할 수가 있어서 유연한 메모리 사용이 가능하다. → 사실상 배열과 가장 큰 차이
• 추가, 삭제가 빠름 : 배열의 경우는 추가, 삭제가 불가능 하므로 ArrayList와 비교를 하면 연결리스트가 더 빠르다
• 인덱스 접근 느림 : 연결 리스트는 n번째 요소에 접근하려면 순서대로 노드를 찾아가야 하므로(O(n)) 배열에 비해 인덱스 접근이 느리다. 배열은 시작 주소와 오프셋을 통해 인덱스의 빠른 접근이 가능하다(O(1)).

종류

단순 연결 리스트 (Singly Linked List)

• 가장 기본적인 연결 리스트이다.
• 다음 노드를 가리키는 t_list *next와 데이터 필드로 이루어진다.
• 맨 뒤의 데이터를 조회할 때는 size 만큼의 시간이 필요하다.
• 정의 구현

typedef struct s_list
{
	void *data;
	struct s_list *next;
} t_list;

양방향 연결 리스트 (Doubly Linked List)

• 한 노드에서 링크가 양방향(이전, 다음)으로 연결 돼있는 리스트다.
• 가장 큰 장점은 노드 탐색이 양방향으로 가능하다는 점이다.
• 인덱스 접근을 할 때, size / 2 이상의 인덱스를 접근할 경우, 뒤에서부터 접근하면 되므로 탐색 시간이 최대 반까지 줄어든다.
• 단점은 이전 노드를 저장하기 위한 메모리를 하나 더 쓴다는 것이다.
• 링크 필드가 t_list *next와 t_list *prev로 이루어진다.
• 정의 구현

typedef struct s_dlist
{
	void *data;
	struct s_dlist *prev;
	struct s_dlist *next;
} t_sdlist;

원형 연결 리스트 (Circular Linked List)

• 단방향 연결 리스트에서 테일 노드의 next가 헤드 노드를 가리키는 형태이다.
• 모든 노드의 링크 필드의 값이 NULL이 아니다.
• 검색을 하다가 중단한 위치에서 검색을 이어갈 수 있다.
• 정의 구현

typedef struct s_clist
{
	void *data;
	struct s_clist *next;
} t_clist;

원형 양방향 연결 리스트 (Doubly Circular Linked List)

• 양방향 연결 리스트에서 테일 노드의 next가 헤드 노드를 가리키는 형태이다.
• 모든 노드의 링크 필드가 NULL이 아니다.
• 기본 리스트에 비해 접근성이 뛰어나다.
• 정의 구현

typedef struct s_dclist
{
	void *data;
	struct s_dclist *prev;
	struct s_dclist *next;
} t_dclist;