[자료구조] Linked List - (1) 개념

리스트는 데이터에 순서를 매겨 늘어놓은 자료구조.

리스트라는 자료구조는 구현 방법에 따라 크게 2가지로 나뉨

1. 순차 리스트 (Array list) : 배열을 기반으로 구현된 리스트
2. 연결 리스트 (Linked list) : 메모리의 동적 할당을 기반으로 구현된 리스트

본 글에서는 연결 리스트에 대해 다룸.

 

Array List와 Linked List의 메모리 사용 비교(출처 : 생활코딩)

미리 정해진 크기(위 그림에서는 노란색 9칸) 에 순차적으로 저장되는 Array List와 달리,
Linked List는 미리 공간의 크기가 정해져있지 않고, 물리적으로 떨어져 있음.

그렇기 떄문에 서로를 연결할 수 있는 방법이 필요.

떨어져 있는 공간을 연결할 수 있는 방법 필요 (출처: 생활코딩)

위 그림에서 노란색 점 하나하나가 아래 그림 linked list 의 Node와 대응됨. Node는 linked list에서 각각의 원소를 의미.

그럼 아래 그림에서 Node1과 Node2는 어떻게 연결할까?

Node 간의 연결 어떻게??

 

각각의 Node는 data와 next 라는 속성을 가짐.

data에는 값이 저장되고, next는 다음에 가리키는 Node에 대한 정보가 들어가 있음. 이를 참조하면 다음 Node에 접근 가능.

 

특별히 맨 앞에 있는 노드를 head node, 맨 끝에 있는 노드를 tail node라고 함.