자료구조 [Linked List]

연결리스트(Linked List) 는 '노드'라는 객체로 이루어져 있는데 각 노드가 데이터와 포인터를 가지고 한줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조가 연결리스트(Linked List)이다.

위 사진처럼 각각의 노드들은 다음 노드의 주소를 값으로 가지고 있는 포인터를 가지고있다.

또한 노드는 연속된 공간에 저장되어 있는 것이 아니라 메모리의 여러 부분에서 분포하여 있다.

노드의 다음주소가 NULL이라면 마지막 노드를 가르킨다.

연결리스트의 장점으로는 삭제나 추가의 시간복잡도가 O(1) 시간에 가능하다.

배열을 보면 5개의 데이터를 가지고있는 배열이 있다고 가정한다면 중간에 하나의 데이터를 삭제하면 나머지 모든 데이터들이 재배치 되어야 한다. 추가 또한 마찬가지로 추가되는 인덱스 다음 모든 데이터들을 재배치 해야하는데

연결리스트는 데이터를 삭제하거나 추가하면 해당 노드의 가르키는 포인터만 변경해 주면 되기 때문에 훨씬 효율적이다.

다만 특정 데이터를 검색하는데 무조건 O(n)의 시간이 걸린다.

배열은 데이터를 찾을 때 인덱스가 있어 검색 효율이 좋지만 연결리스트는 정해진 위치를 알지 못하기 떄문에 검색 시 데이터를 순회해서 특정 데이터를 찾아야 한다.

연결리스트(Linked List)를 구현하기 위해서는 초기화(init) / 삽입(Insert) / 삭제(Remove) 와 같은 함수를 구현해야한다.

✔ 초기화(init)

처음 노드를 생성하는 과정이며 노드에 접근하기 위해서는 맨 처음 노드의 주소를 가리킬 노드가 필요하다.

(맨 처음 노드의 주소를 가리키는 노드를 head라고 표현한다.)

void init() {
    head = NULL;
    tail = NULL;
}

초기화 코드는 위 코드와 같으며 나중에 삽입의 시간복잡도를 줄이기 위해 마지막 노드를 가르키는 노드 end를 같이 생성

초기화 과정에서는 포이터를 NULL로 설정하는데 이는 가르키는 노드가 없다는 의미를 가지고있다.

✔ 삽입(Insert)

1️⃣제일 앞의 원소 삽입

1) 새로운 노드의 링크(포인터)를 헤더의 다음 노드를 가리키도록 해야함

2) head의 링크를 새로운 노드를 가리키게 해야함

❗ 1) , 2) 의 순서가 뒤봐끼면 head의 다음노드를 가리키는 링크(포인터)가 사라지기 때문에 순서를 꼭 지켜야한다.

✔ 삭제(remove)

1️⃣ 제일 앞에 원소 삭제

1) 삭제하고자 하는 원소의 바로 이전 원소를 찾는다.(삭제하고 싶은 원소를 가르키는 원소)

2) 삭제하고 싶은 원소의 이전 원소의 링크를 삭제하고싶은 원소가 가리키는 원소를 가리키도록 한다.

3) 삭제하는 원소를 가리키는 원소가 없기 때문에 쓰레기 처리가 되어 삭제됨.

클린코딩일지