1️⃣ 연결리스트란?
연결리스트는 노드 안에 데이터가 담겨있고 이 노드들이 서로 이어져있는 구조의 자료구조이다.
리스트의 전체적인 구조는 위 그림과 같다.
파란색 네모 하나가 노드이고, 이 노드 안에는 데이터와 다음 노드의 주소를 가리키는 포인터가 들어있어서 서로 이어져 있을 수 있다.
2️⃣ 연결리스트의 종류
연결리스트는 노드 안에 포인터가 어디를 가리키느냐에 따라 리스트의 종류가 나뉜다.
- 단일 연결리스트
포인터가 다음 노드를 가리킨다. - 이중 연결리스트
포인터가 2개이며 각각 이전 노드, 다음 노드를 가리킨다. - 원형 연결리스트
단일 연결리스트와 비슷하나 마지막 노드의 포인터가 맨 앞의 노드를 가리킨다.
출처 : 위키백과 연결리스트
3️⃣ 연결리스트 노드의 구성
설명만으로는 어려울 수 있으니 노드를 하나 만들어보자. 연결리스트는 구조체를 이용해서 만들 수 있다.
1️⃣ 단일 연결리스트의 노드
typedef struct s_node {
int content;
t_node *next;
} t_node;단일 연결리스트는 위에서 설명했던 것처럼 데이터를 담을 수 있는 content를 구조체멤버로 가지고 다음 노드의 주소를 담을 수 있는 next라는 포인터르르 가진다. 여기서 content는 필요에 따라 원하는 데이터로 담을 수 있다.
typedef struct s_student {
char *name;
int age;
char grade;
t_student *next;
} t_student;위 노드는 학생의 이름, 나이, 성적 정보를 담은 단일 연결리스트의 노드이다.
2️⃣ 이중연결리스트의 노드
이중 연결리스트의 노드도 크게 다르지 않다. 단일 연결리스트에서 이전 노드를 가리키는 포인터 멤버가 추가되면 된다.
typedef struct s_node {
int content;
t_node *next;
t_node *prev;
} t_node;4️⃣ 배열과 리스트의 차이
위 설명만 살펴보면 배열과 리스트의 큰 차이가 없어 보인다. 가장 큰 차이는 메모리상의 데이터 순서의 연속성이다.
배열은 메모리상의 데이터 순서가 연속적이고, 리스트는 비연속적이다. 메모리 상에서 데이터의 순서가 연속적이라는 뜻은 데이터 주소가 이어져 있다는 것이다.
배열의 데이터주소는
&arr[0] = 0x00, &arr[1] = 0x01, &arr[2] = 0x03... 이런식으로 구성되어 있고, 반면 연결리스트는 이렇게 연속된 주소를 가지지 않는다.
이 차이점 때문에 데이터의 접근과 삽입 및 삭제하는 방법에서 차이가 나며 배열은 데이터의 조회에는 용이하나, 중간 삽입 및 삭제는 리스트가 더 적합하다.
내가 작성했던 ▶️ [배열과 리스트 중 어떤 것을 사용해야 할까?] 이 글을 보면 더 자세히 공부할 수 있다.
5️⃣ 연결리스트의 시간복잡도
접근, 탐색, 삽입/삭제를 할 때 연결리스트의 시간복잡도는 얼마일까?
1) 접근 : 접근할 때 배열처럼 인덱스로 접근할 수 없으니 해당하는 값이 나올 때 까지 순회해야한다. 최악의 경우 O(n)이 나올 수 있다.
2) 검색 : 가장 앞 노드부터 다음 노드를 하나씩 보면서 탐색하는 선형탐색을 한다. 시간복잡도는 최악의 경우 O(n)이 나온다.
3) 삽입 시간 복잡도
노드의 tail을 알고 있으면 노드의 가장 끝에 데이터를 이어주기만 하면 돼서 O(1)의 시간 복잡도가 걸린다.
하지만 노드의 tail을 알지 못 하거나, 원하는 노드의 뒤에 삽입을 하고 싶다면 리스트의 가장 뒤에 접근하거나 탐색으로 원하는 노드를 찾은 뒤 그 뒤에 삽입해야한다. 그래서 O(n + 1)의 시간복잡도가 걸린다.
4) 삭제 시간 복잡도
마찬가지로 노드의 tail을 알고 있다면 O(1)의 시간복잡도가 걸리고, 특정노드를 삭제하려면 O(n + 1)의 시간복잡도가 걸린다.
