자료구조 기초 개념, 링크드리스트 Linked-list(Python, Java 등)

자료구조 Data Structure의 개념에 대해 간단히 설명해보고자 한다. 시험기간이기에 중간고사 범위에 대한 간략한 정리와 설명을 할 예정이다.

자료구조란 자료를 저장하고 '정렬'을 수월하게 하기 위한 방식이며, 일반적인 코드를 짜는 것보다 효율적으로 코드를 짤 수 있다.

리니어 방식과 non 리니어 방식이 있는데, 리니어에는 linked list, 스택, 큐 등의 방법이 존재하며, non 리니어에는 트리와 그래프 등의 방식이 존재한다. 

논리니어는 시험범위가 아니기에 아직 설명을 할 수는 없고, 우선 리니어 방식의 자료구조에 대해 알아보겠다.

위의 주제 중 스택과 큐, 덱에 관한 글은 문제풀이를 하며 설명을 잠깐 한 적이 있으므로, 이번 시간에는 링크드리스트에 대해 알아보고자 한다.

흔히 리스트를 이용하여 어떠한 자료를 정렬하는 방법에는 array를 이용하는 방식과 linked list 이렇게 두가지로 나뉜다고 볼 수 있을 것 같다. 

array 방식은 메모리에 데이터가 저장될 위치가 '물리적' 으로 연결되어 있고, 그 순서대로 데이터가 차곡차곡 저장되는 방식이다. 따라서 물리적, 논리적 순서가 동일하다.

array 방식의 장점은 index를 통한 조회가 가능하며 빠르다는 것이다. 찾고자 하는 데이터의 위치만 알고있으면, index를 통해 빠른 access가 가능하다. 조회를 하는 경우, 러닝타임은 Big-O(1)가 소요된다. (시간복잡도가 뭔지, 그 종류에 대해서는 중간고사 이후 포스팅하도록 하겠다.)

이 방식의 단점은 데이터의 추가 및 삭제에 있어 너무 많은 시간이 소요된다는 것이다. 

예를 들어 {1,2,4,5}라는 리스트의 2와 4 사이에 3을 추가하려고 한다. 그렇다면 추가를 할 때 5를 오른쪽으로 한칸, 4도 오른쪽으로 한칸 밀어버리고 3을 그 자리에 넣어야 한다. 이는 시간복잡도로 표현하면 Big-O(n)이다. 이 말은 리스트의 길이가 길어지면 길어질수록 밀어야 하는 리스트의 길이도 길어지므로 더욱 긴 시간이 필요하다는 것이다. 삽입 시 빈공간을 만들어 줘야한다는 점과 처음 선언시 크기를 정하고 이를 변경할 수 없다는 것도 치명적인 단점이다.

 

 

 

그렇다면 Linked list는 어떨까? 이 방식은 array의 단점을 보완하기 위해 만들어졌다고 볼 수 있다. 유동적 크기로 인해 자유자재로 크기를 변경할 수 있으며, 연결된 선을 새로 추가되는 데이터에 이어주거나, 제거되는 데이터에서 떼어주는 것만으로도 array와 같은 작업을 할 수 있으므로, 데이터나 시간 측면에서 효율적이다. 이때의 시간복잡도는 Big-O(1)이다.

하지만 단점이라면, Random Access가 불가하다는 점이다. array에서 어떠한 데이터를 찾기위해서 index를 이용하면 손쉽고 빠르게 찾을 수 있었던 것과 다르게, 어떠한 데이터를 찾기 위해서는 처음 head node부터 그 수가 나올때까지 다 찾아봐야한다는 것이다. 만약 원하는 데이터가 운이 나쁘게도 맨 마지막의 tail node에 위치하고 있다면 엄청난 시간이 소모될 것이다. 따라서 특정 요소에 접근하기 위한 시간복잡도는 Big-O(n)이 소요된다.

그리고 각각의 포인터를 저장하는 추가적인 메모리 공간이 필요하다. 이게 무슨 말이냐면, 각 요소마다 데이털르 저장할 공간 외에 다음 요소의 포인터 위치(next)를 저장해야하기 때문에 추가적인 메모리 공간이 필요로 한다.

부족한 설명은 추후 자세한 글과 설명, 예제 등을 적어보도록 하겠다.