패스트캠퍼스 챌린지 39일차

연결 리스트(Linked List)

 

연결 리스트(Linked List)란 유연하게 크기 변경이 가능한 자료구조를 말한다

데이터를 자유롭게 삽입 삭제 할수 있다는 장점이 있다.

집합의 단위를 리스트(List), 각 요소의 단위를 노드(Node)라고 한다.

 

연결 리스트(Linked List)의 구성

리스트는 노드와 노드가 연결(Link)된 형태로 되어 있다.

각 노드는 데이터의 내용을 담는 부분과 다음 노드의 주소값을 갖는 포인터 변수로 구성되어 있다.

리스트의 첫번째 노드를 헤드(Head) 마지막 노드를 테일(Tail)이라고 한다.

단순 연결 리스트(Singly Linked List)는 리스트의 가장 기본적인 형태이다.

다음 사진과 같은 형태이며, 테일의 포인터 변수가 NULL을 가리키는게 특징이다.

 

배열(Array)과의 비교

인덱스 번호와 그에 대응하는 값으로 이루어진 자료구조인 배열과 구분 해 볼 수 있다.

데이터 엑세스 속도는 배열이 리스트보다 빠르다. 배열은 인덱스만 있으면 O(1)에 가능하나, 리스트는 최소 한 번은 순회를 거쳐야 하기 때문에 O(n)이 걸린다.

데이터 삽입과 삭제 속도의 경우 리스트가 배열보다 우위에 있다. 리스트는 어느 곳에 삽입하던지 O(n)에 가능하다. 반면 배열은 중간에 데이터를 삽입 삭제할 경우 기존 데이터들을 이동시켜야 하며, 처음에 지정한 크기를 넘을 경우 새롭게 메모리를 할당 해야 한다.

 

 

 

본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.

https://bit.ly/37BpXiC

패스트캠퍼스 [직장인 실무교육]