Java 데이터 구조 및 알고리즘.쌍사슬시계

소개하다.

이 시리즈는 자바의 데이터 구조와 알고리즘을 배우고 이해하는 데 주력할 것이다.탕 교수는 내가 사용하는 모든 정보는 이 책Data Structures and Algorithms in Java by Michael T. Goodrich and Roberto Tamassia과 캘리포니아주립이공대학 과정HERE에서 나온다고 큰 소리로 말했다. 이 과정은 무료로 찾을 수 있다.이 책을 사지 마세요. 비싸서 인터넷에서 찾을 수 있고 훨씬 싸요.

유튜브 버전:

유튜브에서 이 코드의 버전을 찾을 수 있음HERE

GitHub 코드

코드를 찾을 수 있는 GitHubHERE

무엇이 쌍사슬시계입니까?

단일 체인표에서 각 노드는 그 뒤를 따르는 노드에 대한 인용을 유지한다.이중 링크 목록도 이를 할 수 있다.그러나 이전 노드에 대한 추가 인용이 있습니다.따라서 doubly라고 명명되었다. 한 노드는 두 개의 인용이 있기 때문에 하나는 그 앞의 노드를 가리키고 다른 하나는 그 뒤의 노드를 가리킨다.

첫 번째 노드와 끝 노드.

쌍사슬표 경계 부근에서 조작할 때 특수한 상황이 발생하는 것을 피한다.목록의 양 끝에 특수sentinel nodes를 추가하면 도움이 됩니다.이sentinel 노드들은 메인 링크 목록의 어떤 요소도 저장하지 않고 목록의 크기를 계산하지 않습니다.

왜 보초 노드를 사용합니까?

비록 우리는 당연히 전초 노드가 없는 쌍체인표(예를 들어 단체인표)를 실현할 수 있지만 전초 노드에서 사용하는 추가 메모리는 우리가 목록에서 조작하는 논리를 크게 간소화시켰다.머리와 꼬리는 영원히 변하지 않고 그들 사이의 노드만 바뀐다.이것은 우리가 모든 삽입과 삭제를 통일된 방식으로 처리할 수 있다는 것을 의미한다.

노드 생성

이 노드에는 3개의 실례 변수가 있다:

1) 요소: 이 노드에 저장된 요소에 대한 참조
2) 이전: 이전 노드에 대한 참조
3) 다음: 다음 노드에 대한 참조

node류에 대해 우리는 범주형을 사용하여 클래스에 약간의 유연성을 제공할 것이다.세 개의 실례 변수가 생기면, 우리가 해야 할 일은 POJO (일반적인 옛 자바 대상) 를 만드는 것이다. 따라서 일을 완성하려면 구조 함수, Getter,setter만 만들면 된다.

  public class DoublyLinkedList <E>{
    private static class Node<E>{
        private E element;
        private Node<E> previous;
        private Node<E> next;

        public Node(E element, Node<E> previous, Node<E> next) {
            this.element = element;
            this.previous = previous;
            this.next = next;
        }
        //GETTERS
        public E getElement() {
            return this.element;
        }
        public Node<E> getPrevious(){
            return this.previous;
        }
        public Node<E> getNext(){
            return this.next;
        }
        //SETTERS
        public void setNext(Node<E> next) {
            this.next = next;
        }
        public void setPrevious(Node<E> previous) {
            this.previous = previous;
        }

    }
   }

인스턴스 변수

Node 클래스를 만들면 그 다음에 해야 할 일은 실례 변수를 실현하는 것이다.이 클래스는 세 개의 실례 변수를 포함할 것이다.
1) header: header sentinel 노드에 대한 참조 저장
2) 트레일러: 트레일러 센티넬 노드에 대한 인용 저장
3) 크기: 목록에 몇 개의 노드가 있는지 표시하는 정수 값을 저장합니다

 public class DoublyLinkedList <E>{
// The rest of the node class is above.

        private Node<E> header;
    private Node<E> trailer;
    private int size =0;


}

쌍사슬표 구조 함수

쌍사슬표의 구조기는 매우 중요하다. 왜냐하면 우리는 그것을 사용하여 헤드 노드와 꼬리 노드를 설정하기 때문이다.이것은 단지 우호적인 알림일 뿐이지만, 이 두 sentinel 노드는 코드를 간소화하고 조작 효율을 향상시키는 데 도움이 된다.우선, 우리는 헤더를 만들고, 모든 내용이 비어 있습니다.그런 다음 이전 참조를 제목으로 설정합니다.마지막으로, 우리는 제목의 다음 인용을 트레일러로 설정합니다.따라서 듀얼 링크 목록을 작성할 때 다음과 같은 항목을 작성합니다.

머리와 꼬리는 초병 노드

public DoublyLinkedList(){
        header = new Node<>(null,null,null);
        trailer = new Node<>(null,header,null);
        header.setNext(trailer);
    }

쌍사슬표 방법

우리가 오늘 실현하고자 하는 쌍사슬표는 8가지 방법이 있다(기술적으로는 10가지이지만 우리는 뒤에서 다른 두 가지를 토론할 것이다). 이것은:

1)size(): 목록의 요소 수를 반환합니다.
2) isEmpty(): 목록이 비어 있으면 true를 반환하고 그렇지 않으면 false를 반환합니다.
3) first (): 목록의 첫 번째 요소를 되돌려줍니다.
4) last (): 목록의 마지막 요소를 되돌려줍니다.
5) addFirst(e): 목록 앞에 새 요소를 추가합니다.
6) addLast(e): 목록 끝에 새 요소를 추가합니다.
7)removeFirst(): 목록의 첫 번째 요소를 삭제하고 반환합니다.
8)removeLast(): 목록의 마지막 요소를 삭제하고 반환합니다.

보초 노드의 사용은 몇 가지 측면에서 실현에 영향을 줄 것이다.우선, 우리는 빈 목록을 구축할 때 보초병을 만들고 연결할 것이다.빈 목록이 아닌 첫 번째 요소는 노드의 머리 뒤에 저장되는 것이지 머리 자체가 아니라는 것을 기억해야 한다.그 밖에 마지막 요소는 트레일러 이전의 노드에 저장된다.

우리는 목록의 일반적인 삭제와 삽입을 처리하는 두 가지 개인적인 방법을 만들 것이다.

1) addBetween (): 삽입된 일반적인 상황을 처리하고 addFirst () 와addLast () 에서 호출합니다
2)remove (): 삭제된 일반적인 상황을 처리하려면removeFirst () 와removeLast () 가 호출합니다

우리가 이 유형의 나머지 부분을 실현하기 전에 보초병의 노드는 머리나 꼬리가 아니라는 것을 분명히 설명하고 싶다.그것들은 자신의 가치가 없는 종점을 대표한다.그것들은 간단한 표시를 충당하고 우리의 코드를 간소화한다.

검색 방법 구현

우리가 실현하고자 하는 네 가지 방법은 매우 간단하다. 우리는 size(), isEmpty(), first()와last()를 실현하고 있다.그것들은 목록에서 조작하지 않고, 단지 우리를 위해 값을 검색할 뿐이다.

 public class DoublyLinkedList <E>{
// The rest of the class is above.

        public int size() {
        return this.size;
    }
    public boolean isEmpty() {
        return size == 0;
    }

public E first() {
        if (isEmpty()) {
            return null;
        }else {
            return header.getNext().getElement();
        }
    }
    public E last() {
        if(isEmpty()) {
            return null;
        }else {
            return this.trailer.getPrevious().getElement();
        }
    }

}

업데이트 방법 구현

다음 네 가지 방법은 목록에 노드를 삭제하고 추가하는 데 사용됩니다.이것은addFirst(),addLast(),removeLast(),removeFirst()입니다.그러나 addBetween()과remove()라는 또 다른 두 가지 방법이 있는데 다른 네 가지 방법이 호출될 것이다.이 두 가지 사유 방법 중, 우리는 목록에서 추가하거나 삭제하는 논리를 실현했다.

public void addFirst(E e) {
        addBetween(e,header,header.getNext());
    }
    public void addLast(E e) {
        addBetween(e,trailer.getPrevious(),trailer);
    }
public E removeFirst() {
        if(isEmpty()) {
            return null;
        }else {
            return remove(header.getNext());
        }
    }
    public E removeLast() {
        if(isEmpty()) {
            return null;
        }else {
            return remove(trailer.getPrevious());
        }
    }

대부분의 논리는remove()와addBetween() 방법에 있다.

private void addBetween(E e,Node<E> predecessor, Node<E> successor) {
        Node<E> newest = new Node<>(e,predecessor,successor);
        predecessor.setNext(newest);
        successor.setPrevious(newest);
        size++;
    }

상술한 방법을 사용하면 우리가 진정으로 해야 할 일은 하나의 노드를 만들고 그 다음에 참고 값을 설정하는 것이다.

private E remove(Node<E> node) {
        Node<E> predecessor = node.getPrevious();
        Node<E> successor = node.getNext();

        predecessor.setNext(successor);
        successor.setPrevious(predecessor);

        size--;
        return node.getElement();
    }

논리를 삭제하는 것은 좀 복잡하다. 내가 이렇게 말하는 것은 자바의 본질 때문이다.우리가 removing 하나의 노드일 때, 우리는 실제적으로 다른 노드가 그것을 인용하지 않도록 확보하는 것뿐이다.자바에서 대상이 다른 인용 대상이 없을 때 removed 메모리를 메모리 풀로 되돌려줍니다.그래서 하나의 노드를 제거하는 것은 이렇게 보인다.

결론

시간을 내서 저의 이 박문을 읽어 주셔서 감사합니다.만약 어떤 문제나 걱정이 있으면, 아래에 평론을 발표하거나 저에게 연락 주십시오.