연결 리스트란?

연결 리스트(Linked List)란?

연결 리스트란, 연결 리스트는 각 요소를 포인터로 연결하여 관리하는 선형 자료구조다. 각 요소는 노드라고 부르며 데이터 영역과 포인터 영역으로 구성된다.
추가와 삭제가 반복되는 로직을 배열에 적용하면, 시간 복잡도가 상당히 커지게 된다.
따라서, 추가와 삭제가 반복되는 로직이라면 배열 사용을 권장하지 않는다. (배열은 탐색이 많을 때 유리한 자료구조이다.) 이때 적합한 자료구조는 바로 연결 리스트이다.

그림을 보면, 첫번째 노드를 Head 라고 부르며 각 노드를 알파벳 순으로 적은 부분이 데이터 영역 즉, 해당 노드의 값이라고 할 수 있다. 동그란 회색 영역은 포인터 영역으로 다음 노드를 가리키는 역할을 담당한다.

연결 리스트의 특징

• 메모리가 허용 하는 한 요소를 제한 없이 동적으로 계속해서 추가할 수 있다.
• 탐색의 시간 복잡도는 O(n) 이 소요된다.
• 요소를 추가하거나 제거할 때의 시간 복잡도는 O(1)이 소요된다.
• 연결 리스트의 종류는 단일 연결 리스트(Singly Linked List), 이중 연결 리스트(Doubly Linked List), 원형 연결 리스트(Circular Linked List) 가 존재한다.
  

연결 리스트와 배열의 차이점

배열과 연결리스트는 우선 메모리에서 차이가 발생한다. 배열은 순차적인 데이터가 들어가기에 메모리 영역을 연속적으로 사용한다. 반면, 연결 리스트는 순차적이지 않기에 각 데이터가 퍼져있다. 연결 리스트는 퍼져있는 메모리 영역을 알기 위해 포인터를 사용하여 각 영역을 참조하게 된다.

배열의 요소를 삭제하기 위해서는 선형 시간 O(n) 이 소요된다. 왜냐하면 삭제된 요소의 공백을 메우기 위해 뒷 요소들을 앞으로 당겨야 하기 때문이다. 마찬가지로 배열의 요소를 추가할려면 선형 시간 O(n)이 소요된다.

반면 연결 리스트의 요소 삭제는 상수 시간 O(1) 이 소요된다. 삭제할 요소의 이전 요소가 가리키는 포인터를 삭제할 요소의 다음 요소에 연결한다. 그리고 삭제할 요소를 완전히 삭제하면 연결 리스트의 요소 삭제 로직이 끝난다.

그리고 연결 리스트의 요소 추가는 상수 시간 O(1) 이 소요된다. 추가할 요소를 요소 사이에 끼워넣기 위해
추가할 요소의 포인터를 끼워 넣을 부분의 요소에 포인터를 가리키게 만든다. 그 다음, 끼워넣을 요소의 이전 요소 포인터를 추가된 요소를 가리 키도록 수정한다.