연결리스트 [ Linkedlist . 1]

LinkedList

LinkedList는 연결리스트를 구현한 클래스이다. 

- Vector 와 Arraylist 처럼 List class 를 기반으로 파생한 클래스이다.                                                                  - 선형 자료구조                                                                                                                                    - 노드 하나에 하나의 데이터를 보관하고 노드 내의 링크에 의해 순서정보를 기억하는 자료구조입니다. 

> 신속한 삽입과 삭제를 허용하는 순서리스트 유지에 적합

1. 정렬된 배열에 새 원소 삽입

: 배열 구현의 경우 새 원소보다 큰 원소들을 모두 이동시켜야 함. 

int[] insert( int a[], int n, int x ) {

                 int i = 0; 

                 while ( i < n && a[i] <= x ) {

                                 ++ i ;

                 System.arraycopy(a, i, a, i+1, n-i);

                 a[i];

}

 

2. 간접 참조

* 원소의 실제 위치를 추적하기 위한 보조 인덱스 배열 사용

- 추가의 공간을 필요로 함

- 원소를 이동시킬 필요는 없음

void insert( int[] a, int[] k, int x, int free) {

                      int i = 0;

                      while ( k[i]! = 0 && a[k[i]] < x )

                       i = k[i];

                       a[free] = x;

                       k[free] = k[i];

                       k[i] = free ++ ;

 }