데이터 구조 (3): 링크 의 자바 실현

링크 는 이러한 데이터 구조 로 그 중의 각 대상 은 선형 순서에 따라 배열 된다.체인 테이블 에는 단 방향 체인 테이블, 양 방향 체인 테이블, 질서 있 는 체인 테이블, 무질서 한 체인 테이블, 순환 체인 테이블 과 상기 각 특성 조합의 체인 테이블 등 이 있 는데 체인 테이블 꼬리 동적 집합 은 간단 하면 서도 유연 한 표현 방법 을 제공 했다.
배열 의 선형 순 서 는 아래 표 시 를 통 해 결정 되 는 것 과 달리 링크 의 순 서 는 각 대상 의 지침 에 의 해 결정 된다.일반적인 상황 에서 링크 는 노드 (node) 로 연결 되 어 있 고 모든 노드 에는 다음 노드 (next) 나 이전 노드 (previous) 를 가리 키 는 지침 (또는 참조) 이 있 습 니 다.특수 한 두 노드 에 대해 표 두 노드 의 이전 노드 와 표 꼬리 노드 는 모두 null 에 의 해 표시 된다.노드 를 제외 하고 하나의 체인 시 계 는 시계 헤드 포인터 (L. head) 가 시계 헤드 (head) 를 가리 키 고 표징 이 시작 하 는 곳 을 옮 겨 다 녀 야 한다.시계 헤드 포인터 가 null 을 가리 킬 때 이 링크 가 비어 있 음 을 나타 낸다.
본 고 는 자바 가 간단 한 양 방향 링크 를 실현 했다. Node 류 는 링크 를 구성 하 는 노드 로 그 중에서 key, prev, next 속성 도 있 고 해당 하 는 set, get 방법 도 있다.MyLinkedList 클래스 는 양 방향 체인 테이블 의 실현 클래스 로 가리 키 는 헤더 노드 의 인용 을 포함한다.이번에 실 현 된 insert 작업 은 단지 노드 를 줄 끝 에 간단하게 꽂 는 것 일 뿐 입 니 다.
표 두 와 표 꼬리 의 특수성 으로 인해 링크 의 조작 에 많은 불편 을 가 져 왔 고 경계 처 리 를 간소화 하기 위해 링크 에 보초병 노드 를 설정 할 수 있 으 며 이 노드 는 빈 노드 이다.원래 디자인 에서 null 을 가리 키 는 모든 노드 는 이 보초병 노드 (L. Null 노드) 를 가리 킬 수 있 습 니 다. 이때 L. Null 노드 의 prev 는 꼬리 노드 를 가리 키 고 L. Null 노드 의 next 는 머리 노드 를 가리 킵 니 다.이러한 조정 은 일반적인 양 방향 링크 를 보초병 이 있 는 양 방향 순환 링크 로 바 꾸 었 고 보초병 은 머리 와 꼬리 사이 에 위치 하여 경계 조건 을 없 앴 다.L. Null 의 next 노드 표징 헤드 노드 로 인해 L. head 도 존재 할 필요 가 없습니다.그러나 이렇게 하 는 대 가 는 빈 노드 의 저장 공간 을 지불 하고 짧 은 링크 에 대해 추천 하지 않 으 며 본 고 는 실현 되 지 않 았 다.

 class Node {
    private Node next;
    private Node prev;
    private T key;

    public Node(T key, Node prev, Node next) {
    this.key = key;
    this.prev = prev;
    this.next = next;
    }

    public Node getNext() {
    return this.next;
    }

    public void setNext(Node next) {
    this.next = next;
    }

    public void setprevious(Node prev) {
    this.prev = prev;
    }

    public void setKey(T key) {
    this.key = key;
    }

    public Node getprevious() {
    return this.prev;
    }

    public T getKey() {
    return this.key;
    }

    public String toString() {
    return key.toString();
    }
}

public class MyLinkedList {
    Node head;

    public MyLinkedList() {
    head = null;
    }

    public void insert(T key) {
    if (head == null)
        head = new Node(key, null, null);
    else{
        Node x = head;
        while(x.getNext() != null){
            x = x.getNext();
        }
        x.setNext(new Node(key, x, null));
    }
        
    }

    public Node search(T key) {
    Node x = head;
    while (x != null && !(x.getKey().equals(key)))
        x = x.getNext();
    return x;
    }

    public void delete(T key) {
    Node x = head;
    while (x != null && !(x.getKey().equals(key)))
        x = x.getNext();
    if (x != null) {
        if (head.equals(x)) {
            x.getNext().setprevious(null);
            head = x.getNext();
        } else {
            x.getNext().setprevious(x.getprevious());
            x.getprevious().setNext(x.getNext());
        }
    }
    }

    public void set(T old, T key) {
    Node x = head;
    while (x != null && !(x.getKey().equals(old))){
        x = x.getNext();
    }
    if (x != null)
        x.setKey(key);
    }
}

다음으로 전송:https://www.cnblogs.com/torresliang/p/4775837.html