Arraylist vs Linkedlist

  오랜만의 자료구조 포스팅입니다! 오늘은 연결리스트에 대해 공부한 내용을 정리하고자 합니다. 
 연결리스트는 코딩테스트에서는 잘 쓰이지 않지만 다른 자료구조들을 구현할 때 많이 쓰입니다. 오늘은 이러한 연결리스트가 배열과는 어떤 차이점이 있는지 시간복잡도의 개념과 함께 알아보고자 합니다. 

 

https://codegym.cc/quests/lectures/questsyntax.level08.lecture05

우선, 시간 복잡도는 알고리즘의 최악의 경우의 실행시간을 뜻하며 입력량 N에 비례하여 얼만큼 연산을 많이하는지를 나타냅니다. 이러한 알고리즘의 효율성 척도를 나타낸 것을 또 빅오 표기법이라고 합니다. 표기 방법은 ‘O(N)’ 입니다. 흔히 O(N)이면 N번을 모두 연산 해야하는 경우기 때문에 효율성이 낮다고하고 O(1)이면 데이터의 수에 상관없이 연산횟수가 고정인 유형의 알고리즘으로 효율성이 좋다고 합니다. 

 흔히 배열은 삽입과 삭제시 O(N), 탐색시 O(1) 의 효율성을 가지며 연결리스트는 그 반대입니다. 연결리스트가 삽입삭제시 효율이 좋고 탐색시 효율이 좋지 않은 이유는 다음과 같아요. 여기서는 Random Acccess, 즉 임의접근이 가능한지 아닌지의 개념이 나오는데요, 연결리스트가 자료를 탐색할 시 배열처럼 자료의 어느 중간위치에 임의로 접근하는 것이 불가능해서 원하는 노드를 바로 찾을 수가 없습니다. 연결리스트에서 배열처럼 L[2]로 탐색시 , 컴파일 에러가 발생합니다. 4byte씩 2번째 위치, 즉 8byte의 메모리를 찾아간다고해서 우리가 찾는 노드라는 보장이 없습니다. 따라서 2번 노드에 있는 값을 찾으려면 거기서부터 연결된 1과 0을 모두 거쳐야하기 때문에 N 번째로 가기위해선 N 번을 거쳐야 한다는 O(N) 의 시간복잡도가 나오는 것입니다.  

 연결리스트, 즉 Linked List는 이름에서 느껴지는 바와 같이 데이터들을 서로 가리키며 연결하고있는 형태입니다. 메모리에 첫 할당시 필요한 크기만큼 할당이 되고 그 후  next노드에 연결될 때 또 필요한 만큼 다른 공간에 할당되어 이전 노드와 연결되는 불연속적 형태입니다. 이 때, 한 데이터가 다음 데이터를 가리키면서 그 데이터의 주소값을 본인한테 저장하는 형태로 연결이 되는건데요. 삽입 삭제시에는 이러한 노드 연결작업만 해주면 되기 때문에 시간복잡도가 O(1) 입니다.  

 이렇듯 연결리스트와 배열은 각 목적에 맞게 사용이 용이한 점이 있는 것 같습니다.