[자료구조] 연결 리스트(linked list)

안녕하세요? 코딩충입니다. 

오늘은 연결리스트에 대해서 포스팅하겠습니다.

우선 컴퓨터 데이터 상에 데이터와 포인터를 가진 뭔가(표현을 이렇게 밖에 못하네요ㅜㅜ)가 떠 있습니다.

연결리스트는 이런 '뭔가'들을 포인터로 연결에 만들어진 자료구조입니다.

이 뭔가들을 노드라고 부르겠습니다(원래 정식 명칭이 노드입니다)

이 노드들을 연결하는 방법이 바로 포인터인데 직접 구현하는 것은 나중에 포인터에 대한 포스팅이라 문제 풀이 포스팅에서 설명하겠습니다.

포인터라는 것 자체가 많이 어렵고 복잡하고 내용이 많은 지라..

그래서 이번 포스팅에서는 연결 리스트가 어떤 자료구조인지, 장단점, 어떨때 쓰는지 등을 알아보겠습니다.

https://visualgo.net/ko/ll

위 링크에서 여러가지 버튼들을 눌러보면 연결 리스트가 어떤 자료구조인지를 알 수 있습니다.

출처: 위키피디아

이 연결 리스트가 여러가지 면에서 배열과 대비되는 면이 있는데요 

그런 의미에서 배열과 연결리스트의 장단점을 비교해보도록 하겠습니다.

먼저 배열의 장점으로는 (당연히) 쓰기가 편하고 접근이 편하다는 데 있습니다.

저희가 처음에 코딩을 배울때 가장 먼저 배우는 자료구조(?)가 배열인데요, 이는 배열이 간단히 선언할 수 있고 접근할때도 인덱스와 이름만 알고 있다면 단순하게 접근을 할 수 있다는 데 있습니다.

선언을 할때에도 

(자료형) (이름)[(크기)]; 와 같은 형태로 매우 간단하고 

접근을 할때에는 (값을 사용할때에는)

이름[인덱스] 처럼 사용할 수 있기 때문에 처음에 코딩을 배울때도 그렇고 나중에도 쓰기 편한 자료구조입니다.

하지만 선언하기 편하기 때문에 선언한 후에 크기를 바꾸기가 어렵습니다.

물론 이는 동적 할당을 이용할 수도 있지만 보통의 경우에는 크기를 바꾸기 어렵습니다(사실상 불가능합니다).

또한 접근이 편하기 때문에 삽입이 불편합니다.

삽입을 하기 위해서 삽입하는 위치 뒤의 원소들을 모두 뒤로 옮겨야 하기 때문에 O(N)의 시간복잡도가 쓰입니다.

그래서 삽입과 삭제를 해야 하는 문제를 푸는 경우에는 보통 배열을 사용하지 않습니다.

연결리스트의 장단점이 배열의 장단점과 거의 반대라고 볼 수 있는데요,

연결리스트의 장점인 삽입과 삭제가 편한것이 배열의 단점을 해결한 것인데, 

연결리스트의 단점인 접근이 어려운 것이 배열의 장점입니다.

이와 같이 연결리스트와 배열이 특징이 다르기 때문에 쓰임이 다를 수 밖에 없는데요,

문제의 조건에 맞추어 연결리스트와 배열 (그리고 벡터도 비슷하죠)를 잘 쓰시기를 바라겠습니다.

또한 연결리스트에는 단일 연결 리스트와 이중 연결 리스트, 그리고 원형 리스트가 있는데요 지식 수준이 거기에 미치지 못해(....) 설명을 못해드리겠습니다.

CONTENT BY 코딩충