연결리스트 (Linked List) 기본개념

A라는 [3, 9, -1, 2, 5] 배열이 있을 때 중간에 값을 insert 하려면 데이터값들이 밀리기 때문에

 

많은 시간이 걸리며 Worst case의 경우 n만큼의 시간이 걸려 O(n)의 시간복잡도를 가진다.

 

연결리스트는 순차적 자료구조로, 이런 경우 더 효율적인 연산을 가능하게 해준다.

 

연결리스트(한방향 연결리스트)

가장 기본적인 연결리스트의 구조이며, 각 노드들은 (data값(key값), link(next노드를 가르키는 값))

 

두가지 정보를 담고있다. 그리고 가장 앞의 노드는 head 노드이며, 마지막 노드가 가르키는 값은

 

NULL값이다. 이제 앞에서 O(n)의 시간이 걸렸던 insert 연산을 다시 해보자.

 

B와 C 사이에 K라는 값을 대입하고자 할때,

 

1. K값을 갖는 노드를 하나 만들어주고,
2. B노드를 next를 K노드로, K노드의 next를 C노드로 만들어준다.

이 일련의 과정만 거치면 배열처럼 자료가 밀리는 일 없이 삽입되며 O(1)의 시간복잡도로 해결된다.

 

 

앞서 예로 든것이 연결리스트 중 한방향 연결리스트이며 A는 B를 가르키지만 B는 A에 대한

 

정보를 알 수 없다. 이때 각 노드들은 key값이 한개, 링크가 한개 총 두개의 정보를 가진다.

 

이번에는 한쪽 방향으로 정보를 아는것이 아닌 각 노드들이 양방향으로 정보를 가르키는

 

양방향 리스트이다. 기본적인 구조는 그림과 같으며,

 

양방향 연결리스트

 key값이 1개, 링크 2개 총 3개가 기본 구조고, 헤드 노드와 마지막 노드들은 더미 노드를 가르키고 있다.

 

이 한방향, 양방향 연결리스트들은 각각의 특징이 있고, 상황에 맞게 효율적으로 쓰면된다.