연결리스트

연결리스트 이전에 배열의 장점과 단점에 대해서 먼저 알아두면 좋다!
배열의 장점: 읽기, 쓰기와 같은 참조에서는 0(1) 의 성능을 가진다.
배열의 단점: 크기 예측이 힘들기 때문에 메모리 낭비가 발생할수도 있다. 데이터 삽입,삭제가 비효율적이다.

배열의 단점을 해결 하려면 어떻게 해야할까요 ? 간단합니다! 저장하려는 데이터들을 메모리 공간에 분산해 할당하고 이 데이터들을 서로 연결해 주는겁니다!

이는 노드(Node)라는 것을 만들어서 수행하는데 노드의 구조는 단순합니다. 노드는 데이터 다음 변수 하나와 다음 노드를 가르키는 변수 하나를 가지고 있습니다.

데이터가 필요하다면 필요한 데이터만큼 노드를 만들어 데이터를 저장하고 다른 노드를 가르켜 연결합니다.

이런 구조 때문에 "연결리스트"라고 부르는겁니다.

연결리스트는 첫 노드의 주소만 알고 있으면 다른 모든 노드에 접속 할수있습니다.
또한, 연결이라는 특성 떄문에 배열과는 다른 장단점을 가지고 있습니다.

연결리스트 장점

연결리스트에서 데이터를 추가한다면 빈 메모리 공간 아무곳에 데이터를 생성하고 연결만 해주면 되기 때문에 배열에서 초기 크기를 알아야하는 단점이 연결리스트엔 없습니다. 배열에서 중간에 데이터를 삽입하면 그 뒤에 있는 데이터들은 모두 뒤로 밀려나기 때문에 오버헤드가 많이 일어납니다. 반면 , 연결리스트는 중간에 데이터를 삽입하면 다음 가리키는 노드만 바꿔주면 되기 때문에 아주 간단한 작업입니다.

데이터 삭제도 마찬가지입니다.

연결리스트 단점

배열은 메모리에 연속된 공간에 할당된 공간이 있어서
시작주소만 알면 뒤에 있는 데이터 접근이 쉽습니다. 만약 arr[3] 으로 네번째 데이터에 접근한다면 배열의 시작 주소에서 3을 더한 주소에 바로 접근하기 떄문에 0(1)의 성능을 가집니다. 반면 연결리스트는 데이터들이 전부 떨어져 있기 떄문에 바로 접근할수 없습니다.

네 번쨰 데이터에 접근하고 싶다면 , 첫 번째 노드에서 다음 노드를 찾고 , 또 이 노드도 다음 노드를 찾고 이런 반복을 해서 데이터를 참조합니다.

즉 , 연결 리스트에서 데이터 참조는 O(n)의 성능을 가집니다.

크기

배열 크기: 크기가 고정
연결리스트 크기 : 크기가 동적

주소

배열 주소 : 연속
연결리스트 주소 : 불연속

데이터 참조

배열 데이터 참조 : (배열은 메모리에 연속된 공간에 할당되기 때문에 메모리 접근이 굉장히 바릅니다.) O(1) 의 성능을 가집니다.

연결리스트 데이터 참조: (반면 연결리스트는 데이터 참조하기 위해선 앞에서 부터 해당 노드까지 접근해야 하기 때무넹 조금 느립니다.) O(n) 의 성능을 가집니다.

삽입과 삭제

배열 삽입과 삭제:(기존 모든 데이터를 옮겨야 해서) O(n) 성능

연결리스트 삽입과 삭제:(삽입하려는 노드까지 노드를 계속 타고 들어가야하니) O(n) 의 성능을 가진다.

연결리스트 개념까지 알고 이해 해야하는 부분이 프로그래밍을 할 때 두가지 선택권이 생기는 것이다.

만약에 여러분들이 어떤 프로그램을 만드는데 데이터의 수가 자주 바뀌지 않고 참조가 자주 일어난다면 배열과 연결리스트 중에 어떤 걸 선택해야할까요 ?

물론 둘 중 아무거나 사용해도 상관없지만 성능을 생각한다면 배열이 좀 더 좋은 선택이 될수도 있다.

예를 들어 데이터 삽입과 삭제가 자주 일어나는 데이터의 수가 자주 바뀐다면 배열과 연결리스트중 어떤걸 사용해야할까요 ?
배열은 크기가 고정되어 있어서 메모리 절약을 위해 연결리스트를 사용해야합니다.

어떤 자료구조를 선택하는지에 따라서 데이터의 크기가 작을 경우에는 차이가 별로 없겠지만 데이터가 많아진다면 성능의 차이는 훨신 커질것이다.