자바 데이터 구조의 선형 표

선형 표 는 구성 요소 간 에 선형 관 계 를 가 진 데이터 구조 로 선형 표 에 대한 기본 적 인 조작 은 주로 요 소 를 얻 고 요소 값 을 설정 하 며 옮 겨 다 니 며 삽입,삭제,찾기,교체,정렬 등 이 있다.한편,선형 표 는 순서 저장 구조 와 체인 저장 구 조 를 사용 할 수 있 는데 본 절 은 주로 순서 표,단일 체인 표 와 더 블 링크 의 각종 기본 적 인 조작 을 설명 한다.
1:선형 표 추상 적 인 데이터 형식
선형 표:n(n>=0)개의 데이터 가 같은 요소 로 구 성 된 유한 서열 입 니 다.선형 표 의 정의 인 터 페 이 스 는 다음 과 같다.

public interface IList<T> {
 /**
 *     
 * @return
 */
 boolean isEmpty();
 /**
 *     
 * @return
 */
 int length();
 /**
 *         
 * @param i
 * @return
 */
 T get(int i);
 /**
 *    i     x
 * @param i
 * @param x
 */
 void set(int i,T x);
 /**
 *         x  
 * @param x
 */
 void append(T x);
 /**
 *    i       
 * @param i
 * @return
 */
 T remove(int i);
 /**
 *           
 */
 void removeAll();
 /**
 *           key   
 * @param key
 * @return
 */
 T search(T key);
 void insert(int i,T x);
 /**
 *     
 * @param x
 */
 void insert(T x);
 /**
 *     
 * @param x
 */
 void remove(T x);
}

2:선형 표 순서 표시 와 실현
선형 표 의 순서 저장 구 조 는 연속 적 인 메모리 유닛 이 순서대로 저장 하 는 선형 표 의 데이터 요소 로 요소 의 물리 적 주소 와 논리 적 주소 순 서 는 같다.우 리 는 이런 저장 방식 을 순서 표 라 고 부른다.
배열 은 할당 과 수치 만 할 수 있 고 길 이 는 변화 할 수 없 기 때문에 우리 의 작업 에 큰 번 거 로 움 을 가 져 다 주지 만 순서 표 로 삭제,삽입 등 작업 을 할 수 있 습 니 다.사실 순서 표 내부 에 도 배열 이 적용 되 어 표 시 됩 니 다.다만 이 데 이 터 는 우리 가 그의 길 이 를 바 꿀 수 있 습 니 다.이렇게 말 하면 우 리 는 쉽게 할 수 있 습 니 다.먼저 우 리 는 순서 표 에 하나의 배열 을 정의 하 는 동시에 하나의 값 을 정의 하여 선형 표 의 길 이 를 기록 해 야 합 니 다.그래서 첫 번 째 단 계 는 다음 과 같 습 니 다.

준비 사건 이 끝 난 후에 우 리 는 반드시 순서 표를 초기 화 할 것 이다.방금 시작 한 배열 의 길 이 는 0 일 것 이다.그러나 우 리 는 삽입 할 요 소 를 저장 하기 위해 배열 에 메모리 공간 을 열 어야 합 니 다.다음 과 같 습 니 다.

다른 것 은 모두 비교적 간단 하 다.나 는 주로 삽입 과 삭 제 를 말한다.
하나의 요 소 를 삽입 할 때 i 번 째 위치 에 꽂 으 면 뒤의 모든 요소 의 앞부분 이 뒤로 이동 하 는 것 을 의미 합 니 다.그러나 우 리 는 i 위 치 를 삽입 할 요소 에 남 겨 야 합 니 다.하지만 이 배열 이 꽉 찼 다 면 고려 해 야 한다.만약 가득 차 면,우 리 는 순서 표 에 메모리 공간 을 다시 열 어야 합 니 다.그리고 이전의 요 소 를 새로운 표 로 옮 겨 야 합 니 다.자바 는 다음 과 같 습 니 다.

코드 를 통 해 알 수 있 듯 이 우 리 는 i 번 째 위치 에서 요 소 를 모두 뒤로 이동 시 킨 다음 에 i 번 째 요 소 를 할당 합 니 다.
i 번 째 요 소 를 삭제 합 니 다.이것 은 위의 것 과 정반 대 입 니 다.i 번 째 요 소 를 삭제 하면 i 다음 요소 앞부분 에서 한 자 리 를 앞으로 이동 하 는 것 을 의미 합 니 다.

3:순서 표 조작 효율 분석
순서 표 는 색인 이 있 기 때문에 get()과 set()의 효율 이 매우 높 고 시간 복잡 도 는 모두 O(n)이다.
위 에서 발견 한 바 와 같이 삽입 과 삭제 할 때 대량의 원소 의 이동 이 필요 하 다.각 위치 에 원 소 를 삽입 할 확률 이 같 기 때문에 평균 적 으로 원 소 를 삽입 하여 이동 할 원 소 는 2/n 이다.그러면 시간 복잡 도 는 O(n)이다.용기 가 가득 차 려 면 새로 추 가 된 요 소 를 저장 하기 위해 더 큰 용 기 를 신청 해 야 한다.그러면 효율 이 더욱 떨어진다.그래서 순서 표 의 정태 성 이 좋 고 동태 성 이 떨 어 지기 때문에 선택 할 때 주의해 야 한다.
4:단일 체인 시트 의 실현
선형 표 의 체인 저장 구 조 는 몇 개의 주소 로 분 산 된 저장 장치 로 데이터 요 소 를 저장 하 는 것 으로 논리 적 으로 인접 한 2 개의 요소 로 물리 적 주소 가 반드시 같 지 않다.그러면 메모리 의 주 소 를 충분히 이용 할 수 있다.그러나 우 리 는 2 개의 서로 다른 데이터 요 소 를 추가 정보 로 연결 해 야 하기 때문에 2 개의 개념,데이터 필드(data)와 주소 필드(next)를 도입 했다.그 중에서 데이터 도 메 인 은 이 요소 의 값 을 저장 하고 주소 도 메 인 은 다음 요소 의 주 소 를 저장 했다.그 중에서 데이터 필드 와 주소 필드 가 결합 하면 우 리 는 노드(node)라 고 부른다.만약 에 후계 노드 만 전구 노드 가 없다 면 우 리 는 단일 체인 표 라 고 부른다.그러면 지금 우 리 는 단일 체인 표 의 실현 을 살 펴 보 자.
우선 노드 노드 노드 를 정의 해 야 합 니 다.

public class Node<T> {
 public T data;//   
 public Node next;//   
 public Node() {
 this(null, null);
 }
 public Node(T data, Node next) {
 this.data = data;
 this.next = next;
 }
}

지금 우 리 는 A(x)와 B(y)두 개의 노드 를 상상 해 보 자.그 중에서 A 의 후계 노드 는 B 이다.그러면 우 리 는 어떻게 표현 할 까?다음 과 같다.

Node<String> A=new Node<T>(x,null);
Node<String> B=new Node<T>(y,null);
A.next=B。

A 를 NodeA=new Node(x,B)로 쓸 수도 있다.
ok 이제 우 리 는 머리 노드 가 있 는 단일 체인 표를 본 격 적 으로 실현 하기 시작 했다.
우 리 는 머리 지침 을 하나의 지침 으로 상상 하여 우리 의 조작 에 편리 하 게 할 수 있다.우 리 는 먼저 어떻게 단일 체인 표 의 길 이 를 실현 하 는 지 볼 수 있다.

public int length() {
 int i = 0;
 Node<T> p = this.head.next;
 while (p != null) {
  p = p.next;
  i++;
 }
 return i;
 }

이것 은 체인 식 의 구조 이기 때문에 우 리 는 길 이 를 알 수 없고 순환 을 통 해 체인 테이블 의 노드 의 개 수 를 알 수 있다.왜냐하면 헤드 포인터 의 후계 노드 가 바로 우리 체인 테이블 의 첫 번 째 노드 이기 때문에 우 리 는 이렇게 아래로 순환 해서 알 수 있다.
i 번 째 노드 의 값 가 져 오기
마찬가지 로 우 리 는 노드 를 직접 얻 을 수 없습니다.이 럴 때 도 순환 을 사용 합 니 다.만약 에 i 번 째 요소 값 이 우리 i 와 같다 면 우 리 는 이 노드 를 얻 은 다음 에 값 을 얻 습 니 다.

public T get(int i) {
 if (i >= 0) {
  Node<T> p = this.head;
  for (int j = 0; j <= i; j++) {
  p = p.next;
  }
  if (p!=null){
  return p.data;
  }
 }
 return null;
 }

i 번 째 위치 에 노드 를 삽입 합 니 다.
먼저 우 리 는 노드 를 삽입 할 전구 노드 를 찾 아야 한다.그 다음 에 전구 노드 의 후계 노드 는 이 새로운 노드 를 가리 키 고 새로운 노드 의 후계 노드 는 원래 의 전구 노드 의 후계 노드 를 가리킨다.

코드 를 보면 우 리 는 머리 노드 에 따라 순환 하 는 것 을 알 수 있다.p.next 가입!=null 의 목적 은 마지막 노드 로 순환 할 때 멈 추고 계속 하지 않 기 위해 서 입 니 다.
제 i 노드 제거
만약 에 우리 가 i 번 째 노드 를 삭제 하려 면 위 와 차이 가 많 지 않 습 니 다.마찬가지 로 우 리 는 이 i 번 째 노드 의 전구 노드 를 찾 아야 합 니 다.위 코드 와 차이 가 많 지 않 습 니 다.

링크 뒤에 노드 를 추가 합 니 다.
전통 적 이면 insert(this.length,x)를 사용 할 수 있 습 니 다.그러나 이렇게 되면 길 이 를 계산 할 때 링크 를 옮 겨 다 니 며 속도 가 느 려 지고 다음 과 같다.
insert(Integer.MAX_VALUE,x)하면 됩 니 다.코드 를 삽입 하면 마지막 노드 로 순환 하면 계속 되 지 않 고 새로운 노드 를 마지막 에 추가 하면 됩 니 다.
5:정렬 싱글 체인 시트
정렬 은 우선 우리 의 요소 가 comparable 을 계승 해 야 합 니 다.
삽입 하고 삭제 하 라 고.먼저 말 하고 삽입 하 다
요 소 를 삽입 하면 이 노드 를 삽입 할 전구 노드 와 후계 노드 를 가 져 옵 니 다.(x.compareTo(y)<0 은 y 보다 작 음 을 나타 낸다)

그 중에서 p.data.next.com pareto(x)<0 순환 설명 p 절 점 치가 x 보다 크 거나 같 으 면
하나의 요 소 를 삭제 하면 위의 기본 과 같 지만 판단 을 더 하면 다음 과 같다.

그 중에서 상기 판단 을 통 해 우 리 는 p 노드 가 x 노드 보다 크 거나 같 음 을 알 기 때문에 다시 판단 해 야 한다.
6:단일 링크 작업 효율 분석
단일 체인 시트 는 요소 와 설정 요 소 를 가 져 올 때 옮 겨 다 녀 야 하기 때문에 시간 복잡 도 O(n)
p 노드 에 요 소 를 삽입 하거나 삭제 하면 체인 의 후계 노드 의 주 소 를 수정 하면 됩 니 다.그래서 시간 복잡 도 O(1)입 니 다.그러나 insert(i,x)와 유사 한 삽입 을 하면 옮 겨 다 녀 야 합 니 다.그러면 시간 복잡 도 는 O(n)입 니 다.
단일 체인 표를 삽입 하고 삭제 하려 면 소량의 노드 의 체인 만 바 꾸 고 이동 요 소 를 필요 로 하지 않 는 다.단일 체인 표 의 삽입 과 삭 제 는 모두 동적 신청 과 방출 된 것 이기 때문에 저장 공간 을 미리 분배 하지 않 아 도 저장 공간 이 부족 해서 확대 되 지 않 고 운행 효율 을 높 일 수 있다.
7:더 블 링크 의 실현
더 블 링크 와 싱글 링크 는 대부분이 같은 것 이 고 전구 노드 가 많 을 뿐 입 니 다.지금 우 리 는 먼저 더 블 링크 를 정의 합 니 다.

순환 더 블 링크 의 실현 을 보 여 드 리 겠 습 니 다.기본적으로 단일 체인 시트 와 같 습 니 다.다만 빈 링크 라면 그의 후계 노드 는 머리 노드 입 니 다.OK.일단 보 겠 습 니 다.

더 블 링크 의 길 이 를 구 합 니 다.

저 희 는 삽입 과 삭제 만 말 합 니 다.
끼어들다
마찬가지 로 우 리 는 삽입 할 노드 를 찾 아야 한다.

그 중 p.next!=this.head 는 마지막 노드 라면 순환 을 뛰 어 넘 는 것 을 나타 낸다.그 중에서 삽입 할 노드 는 p 노드 후에 우 리 는 쉽게 이해 할 수 있다.
삭제
위의 것 과 차이 가 많 지 않다

8:순환 더 블 링크

싱글 체인 시계 랑 똑 같 아 요.또한 노드 의 위 치 를 먼저 찾 아서 삽입 하거나 삭제 합 니 다.
요약:주로 선형 표를 돌 이 켜 보고 선형 표 에 대한 이 해 를 통 해 앞으로 자바 용기 소스 코드 를 볼 때 큰 도움 이 될 것 입 니 다.
이상 은 본 고의 모든 내용 입 니 다.본 고의 내용 이 여러분 의 학습 이나 업무 에 어느 정도 도움 이 되 기 를 바 랍 니 다.또한 저 희 를 많이 지지 해 주시 기 바 랍 니 다!