연결리스트

리스트

리스트란?

리스트는 다른 나중에 배울 Stack, Queue, Tree, Graph 등과 같은 다른 자료구조 구현에 활용될 기초 자료구조이다.

리스트 특징

• 자료를 순서대로 한 줄로 저장하는 자료구조
• 여러 자료가 일직선으로 서로 연결된 선형 구조
• 제일 처음 데이터를 가리켜서 Head라고 한다.
• 제일 마지막 데이터를 가리켜서 Tail이라고 한다.

리스트 종류

'구현방식'에 따라

• 배열 리스트
• 연결 리스트

배열 리스트란?

배열을 사용해 구현된 리스트

물리적 주소를 바로 계산할 수 있어 리스트의 특정 위치에 바로 접근할 수 있다.

연결 리스트란?

node의 연결로 이루어진 리스트로 원소들 간의 논리적 순서를 위한 자료구조이다.

연결 리스트는 위의 그림과 같이 여러개의 node를 연결함으로써 데이터를 표현가능하다. 노드는 자료를 가진 data 부분과 다음 노드를 연결하는 link 부분으로 나뉘어져 있다. 배열과 유사하지만 훨씬 효율적인 저장 방법이다.

배열과 차이점

배열은 - 정해진 메모리크기를 미리 할당 하기때문에 오버플로우나 공간 낭비가 발생가능하다.
연결 리스트는 - 필요한 만큼 메모리를 동적으로 할당 받아서 만든다.

연결 리스트 종류

• Singly linked list
  노드 맨앞에 head node 를 넣어 삽입, 삭제 등 연산에서 이점을 만듬.
  
• Circularly linked list
  마지막 노드가 다시 처음 노드를 가리킴.
  
• List with a header node
  노드 맨앞에 head node 를 넣어 삽입, 삭제 등 연산에서 이점을 만듬.
  
• Doubly linked list
  노드를 연결하는 link가 앞 뒤로 존재해서 앞 뒤 노드들 간의 관계를 바로 확인할 수 있다.