[알고리즘] 리스트

< 리스트 >

• 순서를 가진 데이터의 집합을 가리키는 추상자료형
• 동일한 데이터를 가지고 있어도 상관없다.

     종류

• 배열을 기반으로 구현된 리스트인 순차리스트
• 메모리의 동적할당(JVM의 객체 생성)을 기반으로 구현된 리스트인 연결리스트

---

     < 순차 리스트 >

• 1차원 배열에 항목들을 순서대로 저장한다.
• 데이터의 종류와 구조에 따라 구조화된 자료구조를 만들어 배열로 만들 수도 있다.
• 배열의 인덱스를 이용해 원하는 위치의 데이터에 접근할 수 있다.

      문제점

• 단순 배열을 이용해 순차리스트르 구현해 사용하는 경우, 자료의 삽입/삭제 연산 과정에서 연속적인 메모리 배열을 위해 원소들을 이동시키는 작업이 필요하다.
• 원소의 개수가 많고 삽입/삭제 연산이 빈번하게 일어날수록 작업에 소요되는 시간이 크게 증가한다.
• 배열의 크기가 정해져 있는 경우, 실제로 사용될 메모리보다 크게 할당하여 메모리의 낭비를 초래할 수도 있고, 반대로 할당된 메모리보다 많은 자료를 사용하여 새롭게 배열을 만들어 작업을 해야하는 경우가 발생할 수도 있다.

---

     < 연결 리스트 >

• 자료의 논리적인 순서와 메모리 상의 물리적인 순서가 일치하지 않고, 개별적으로 위치하고 있는 원소의 레퍼런스를 연결하여 하나의 전체적인 자료구조를 이룬다.
• 링크를 통해 원소에 접근하므로, 순차 리스트에서처럼 물리적인 순서를 맞추기 위한 작업이 필요하지 않다.
• 자료구조의 크기를 동적으로 조정할 수 있어, 메모리의 효율적인 사용이 가능하다.

노드 : 연결리스트에서 하나의 원소에 필요한 데이터를 갖고 있는 자료 단위

1) 데이터 필드 - 원소의 값 저장, 원소 종류나 크기에 따라 구조 정의하여 사용

2) 링크 필드 - 다음 노드 주소 저장

   

헤드 : 리스트의 처음 노드를 가리키는 레퍼런스

헤드가 가장 앞 노드를 가리키고, 링크 필드가 연속적으로 다음 노드를 가리킨다. 최종으로 NULL을 가리키는 노드가 리스트의 가장 마지막 노드이다.

 

• 중간에 노드 삽입하는 법

① 메모리를 할당하여 새로운 노드 생성

② 새로운 노드에 데이터 저장

③ 새로운 노드 next가 삽입 위치의 다음 노드 가리킴

④ 삽입 위치 바로 앞 노드 next가 새로운 노드를 가리킴

 

---

      < 이중 연결 리스트 >

• 양쪽 방향으로 순회할 수 있도록 노드를 연결한 리스트
• 이전 노드 가리키는 링크 필드와 다음 노드 가리키는 링크 필드, 한 개의 데이터 필드로 구성