List 자료구조

순서를 가진 데이터의 집합을 가리키는 추상자료형(abstract data type)

- 중복 데이터 가능

- 순차 List (배열 기반)와 연결 List(메모리 동적할당 기반)로 이루어짐

 

 

 

1. 순차 List

- 1차원 배열에 항목 순서대로 저장

- 배열의 인덱스를 이용해 원하는 위치에 접근

 

(1) 연산 종류

- 삽입 연산 : 삽입 위치 다음의 항목들 모두 이동!! (뒤에서부터 이동)

- 삭제 연산 : 삭제 위치 다음의 항목들 모두 이동!! (앞에서부터 이동)

⇒ 작업 소요 시간 크게 증가

 

(2) 단점

메모리 낭비 초래 : 실제로 사용될 메모리보다 크게 할당

 

 

 

 

 

 

2. 연결List

- 개별적으로 위치하고 있는 원소의 주소를 연결

- 링크를 통해 원소에 접근 --> 물리적 순서 맞추는 작업x

 

(1) 구성요소

- 노드 : 하나의 원소에 필요한 데이터를 갖고 있는 자료 단위 (데이터 필드 + 링크 필드)

- 헤드 : 리스트의 처음 노드를 가리키는 자료구조

 

 

(2) 장단점

- 장점 : 메모리 효율성 (자료구조 크기 동적 조정 가능)

- 단점 : 구현 복잡

 

 

(3) 종류

[단순 연결 LIST]

하나의 링크 필드에 의해 다음 노드와 연결되는 구조 / NULL 가리키는 원소가 마지막

- 삽입

• addToFirst : 추가할 노드의 next에 head 노드 연결 + head 변경
• add : pre 노드의 next에 추가할 노드 연결 + 추가할 노드의 next에 pre.next를 연결
• addToLast : 마지막 노드의 next에 추가할 노드 연결

- 삭제 : 삭제할 노드의 링크 필드를 선행노드의 링크에 복사

 

 

[이중 연결List]

양쪽 방향으로 순회할 수 있도록 연결한 list (두개의 링크 필드 + 1개의 데이터필드)

 

- 삽입

• addToFirst : node의 next에 head 연결 + head의 prev에 node 연결 + head 변경
• add
  • node의 next에 cur의 next 연결
  • cur의 next에 node 연결
  • node의 prev에 cur 연결
  • node.next의 prev에 node 연결

 

• addToLast : 마지막 노드의 next에 node 연결 + node의 prev에 마지막 노드 연결

※ node를 삽입할 노드라고 지칭

 

- 삭제

• cur.prev의 next에 cur.next를 연결 (단, cur의 prev가 null이 아닐 때)
• cur.next의 prev에 cur.prev를 연결 (단, cur의 next가 null이 아닐 때)