[자료구조] Linked list 연결리스트

제가 알고 이해한 것들만 작성하였습니다. 절대 정답이 아님을..

 

Linked list

일렬로 연결된 데이터를 저장할 때 사용

데이터를 저장할 수 있는 공간 안에 다음 데이터의 주소를 가지고 있는 구조

 

 이미지출처 https://en.wikipedia.org/wiki/Linked_list

 

 

array와 linked list

 

array

- 크기를 한번 정하면 늘이거나 줄일 수 없다. (삽입 및 삭제 시 새로운 배열을 만들어 데이터를 복사해야한다)

- 데이터가 인덱스에 저장되기 때문에 검색이 쉽다. (시간복잡도 O(1))

 

linked list

- 데이터끼리 연결하는 구조라서 삽입과 삭제 시 연결만 잇고 자르면 된다.

- 데이터 검색 시 첫 데이터부터 다음 데이터를 훑어야 하기 때문에 시간이 오래 걸린다. (시간복잡도 아마 O(n))

 

 

linked list 에서의 삽입

이미지 출처 https://en.wikipedia.org/wiki/Linked_list

리스트를 뭐 어케 건들고 바꾸고 할 것 없이 들어갈 자리의 링크를 내가 먹고 내 링크를 그 다음 노드에게 주면 된다.

 

 

linked list 에서의 삭제

이미지 출처 https://en.wikipedia.org/wiki/Linked_list

삭제할 노드의 이전 노드를 찾아 이전 노드의 링크를 삭제할 노드의 다음 노드에 잇는다.