LinkedList의 정의와 구조

LinkedList의 개념과 종류

• LinkedList의 개념을 알아보기 전에 배열에 대해서 먼저 알아보도록 하자.
• 배열(Array)은 동일한 자료형을 연속적인 메모리 공간에 저장하는 자료구조이다. 연속적인 메모리 공간에 저장되기 때문에 무작위 접근(Random Access)가 가능하다. 대신 초기에 설정해놓은 크기를 조절하기가 불가능하며 데이터의 삽입 삭제 연산 속도가 느리다.
• 연결 리스트는 배열의 단점을 해결하기 위해 나온 개념으로 연속적인 메모리 공간에 저장하는 것이 아닌 여러 메모리 공간에 저장한다. 그렇다면 이를 어떻게 리스트처럼 연결할까가 문제가 된다.
• 연결 리스트는 현재 데이터의 다음 데이터가 메모리의 어느 위치에 존재하는지에 대한 데이터 next 를 가지고 있다. 따라서 데이터를 접근할 때 next를 찾아 그 주소로 이동하는 것으로 다음 데이터로 이동할 수 있게 된다.
• 대신 데이터들이 연속적으로 위치하지 않기 때문에 무작위 접근이 불가능하다. 반드시 시작부터 끝까지 next를 통하여 순회하여 찾아야 하는 불편함이 존재하게 된다.
• LinkedList는 단방향 연결 리스트(Single Linked List), 양방향 연결 리스트(Double Linked List), 환형 연결 리스트(Circler Linked List)로 분류된다.

 

LinkedList의 구조

• 가장 단순한 구조인 Single Linked List는 데이터를 가지고 있는 객체인 Node, LinkedList의 시작점인 head로 구성된다.
• Node는 내부적으로 데이터를 저장하는 공간과 자신의 다음 Node의 위치를 가지고 있는 next로 이루어져 있다.

노드의 구조

• head는 LinkedList의 첫 원소를 가리키고 있는 데이터로 정의된다. 즉, LinkedList의 첫 번째 데이터가 존재하는 주소를 가지고 있는 데이터이다.

 

 

LinkedList의 연산

• LinkedList는 다음과 같은 연산들을 가지고 있다
  • 노드의 삽입
  • 노드의 삭제
• 삽입과 삭제는 임의의 위치에 존재하는 노드도 대상이 될 수 있다. 다음 편에서 단방향 연결 리스트의 연산들을 구현해볼 것이다.