리스트

선형 리스트(Linear List)

• 선형 리스트는 배열과 같이 연속되는 기억장소에 저장되는 리스트를 말한다.
• 연접 리스트(Dense List) 또는 축차 구조(Sequential Structure)라고도 한다.
• 선형 리스트의 대표적인 구조 : 배열(Array)

특징

• 가장 간단한 자료 구조
• 접근 속도가 빠름
• 중간에 자료를 삽입하기 위해서는 연속된 빈 공간이 있어야 함
• 기억장소를 연속적으로 배정받기 때문에 기억장소 이용 효율은 밀도가 1로서 가장 좋다.
• 자료의 개수가 n개 일때 삽입시의 평균 이동 횟수는 (n+1)/2이고, 삭제 시 에는 (n-1)/2이다
• 삽입, 삭제 시 자료의 이동이 필요하여 작업이 번거롭습니다.

---

연결 리스트(Linked List)

연결 리스트는 자들을 반드시 연속적으로 배열시키진 않으며 임의의 기억공간에 기억을 시키나, 자료 항목의 순서에 따라 노드의 포인터 부분을 이용해 서로 연결시키는 자료구조입니다.

 

연결 리스트의 특징

• 노드의 삽입, 삭제 작업이 용이함
• 기억공간이 연속적으로 놓여있지 않아도 저장이 가능
• 연결을 위한 링크(포인터)부분이 필요하기 때문에 순차 리스트에 비해 기억공간 이용 효율이 나쁨
• 연결을 위한 포인터를 찾는 시간이 필요해 접근 속도가 느립니다.
• 중간 노드 연결이 끊어진다면 그 다음의 노드를 찾기가 어렵습니다.
• 희소 행렬(많은 항들이 0으로 되어있는 형태)을 링크드 리스트로 표현하면 기억장소가 절약됨
• 트리를 표현할 때 가장 적합한 자료구조입니다,