데이터구조-리스트(List)

*데이터구조-리스트(list)

-데이터를 일직선으로 나열한 형태

-(장)데이터의 추가, 삭제가 쉬움

-(단)원하는 데이터 접근 시 시간이 많이 걸림

 

*순차접근 리스트(sequential access)

-가장 기본적인 형태의 리스트

 

-순차접근 리스트의 예

-세 개의 문자열(파랑, 노랑, 빨강)의 데이터가 저장되어 있을 때

-각 데이터에는 포인터(pointer)가 있으며 다음 데이터의 메모리 위치를 가리킴

-파랑 --(포인터)--> 노랑 --(포인터)--> 빨강

-(마지막 데이터의 포인터는 아무것도 가리키지 않음)

 

-순차접근 리스트 위치 및 접근

-리스트에서 데이터가 메모리상의 연속된 위치에 저장되지 않아도 됨

-일반적으로 떨어진 영역에 흩어져 저장되어 있음

-흩어져 저장된 데이터들은 포인터를 처음부터 순서대로 따라가야만 원하는 데이터에 접근할 수 있음

-(빨강에 접근하고 싶은 경우 먼저 파랑에 접근한 다음 노랑에 접근해야 함)

 

-순차접근 리스트 데이터 추가

-추가할 위치의 앞뒤 포인터를 변경하면 됨

-파랑과 노랑 사이에 초록을 추가하고 싶을 때

-파랑의 포인터를 초록을 가리키고, 초록의 포인터를 노랑을 가리키도록 하면 됨

 

-순차접근 리스트 데이터 삭제

-포인터의 방향을 바꾸면 됨

-노랑을 삭제하는 경우

-초록의 포인터를 노랑이 아닌 빨강을 가리키도록 변경하면 됨

-노랑의 데이터는 메모리에 남아있지만 접근할 수 없으므로 일부러 삭제할 필요가 없음

-이후 노랑의 영역은 사용될 때 덮어쓰기가 되어 다시 사용할 수 있음

 

*원형 리스트

-마지막 데이터의 포인터가 선두를 가리키도록 한 리스트

-원형 리스트는 선두나 후미라는 개념이 없음

 

*양방향 리스트

-각 데이터가 포인터 두 개을 사용해 앞뒤 데이터를 가리키도록 한 리스트

-(장)리스트를 앞에서 뒤로, 뒤에서 앞으로 추적할 수 있어 편리함

-(단)포인터 수가 늘어나 데이터 저장을 위한 영역이 많아져 데이터 추가 및 삭제 시 변경해야 될 포인터가 늘어남

 

 

 

 

 

---

이 포스팅에 작성한 내용은 이시다 모리테루, 미야자키 쇼이치, ⌜알고리즘 도감⌟, 김완섭 옮김, (주)제이펍, 2020 에서 발췌하였습니다.