[데이터 구조] 싱글 체인 시트, 더 블 엔 드 링크, 질서 있 는 링크

단 방향 링크
더 블 엔 드 링크
질서 있 는 링크

LeetCode 를 칠 할 때 링크 의 제목 인 Merge Two Sorted Lists 를 만 났 는데 자신 이 답 을 알 아 보지 못 한 다 는 것 을 알 게 되 었 다 (데이터 구 조 를 체계적으로 학습 하지 않 았 기 때문에 T T).
그래서 데이터 구조의 학습 을 열심히 실천 하기 로 마음 먹었다.링크 는 배열 에 비해 데이터 삽입 과 삭제 효율 이 높다.어떤 노드 에 무 작위 로 접근 하 는 데 이 터 는 배열 보다 빠 릅 니 다.
다음은 자바 가 실현 한 각종 링크 입 니 다.
단 방향 링크
링크 의 조작 을 바느질 에 비유 하면 선 은 모든 노드 간 의 next 침 은 복 제 된 모든 지향 노드 의 Data 이다.
넥 스 트 가 '=' 의 왼쪽 에 나타 나 야만 링크 의 구조 가 실질 적 으로 바 뀔 수 있다.
insertFirst: 표 머리 에 새로운 노드 를 삽입 합 니 다. 시간 복잡 도 는 O (1) deleteFirst 입 니 다. 표 머리의 노드 를 삭제 하고 시간 복잡 도 는 O (1) 입 니 다. 이 두 가지 방법 이 있 으 면 하나의 스 택 을 단일 체인 표 로 실현 할 수 있 습 니 다. find: 지정 한 키 워드 를 포함 하 는 노드 를 찾 습 니 다. 두루 찾 아야 하기 때문에 평균 N/2 번, 즉 O (N) 를 찾 아야 합 니 다.remove: 지정 한 키 워드 를 포함 하 는 노드 를 삭제 합 니 다. 검색 을 옮 겨 다 녀 야 하기 때문에 평균 N/2 번, 즉 O (N) 를 찾 아야 합 니 다.

public class LinkedList {

    public static void main(String[] args) {

    }

    class Data{
        Object obj;
        Data next = null;
        Data(Object obj){
            this.obj = obj;
        }
    }

    Data first = null;
    //     
    public void insertFirst(Object obj){
        Data data = new Data(obj);
        data.next = first;
        first = data;
    }
    //     
    public Object deleteFirst()throws Exception{
        if(first==null)
            throw new Exception("empty");
        Data temp = first;
        first = first.next;
        return temp.obj;
    }
    //           
    public Object find(Object obj)throws Exception{
        if(first==null)
            throw new Exception("empty");
        Data cur = first;
        while(cur!=null){
            if(cur.obj.equals(obj))
                return cur.obj;
            cur = cur.next;
        }
        return null;
    }
    //        
    public boolean isEmpty(){
        return first==null;
    }
    //              
    public void remove(Object obj)throws Exception{
        if(first==null)
            throw new Exception("empty");
        if(first.obj.equals(obj)){   //  
            first = first.next;
        }else{
            Data pre = first;
            Data cur = first.next;
            while(cur!=null){
                if(cur.obj.equals(obj)){
                    pre.next = cur.next;
                    break;
                }
                pre = cur;
                cur = cur.next;
            }
        }
    }
    //             
    public void removeAll(Object obj)throws Exception{
        if(first==null)
            throw new Exception("empty");
        while(first.obj.equals(obj)){
            first = first.next;
        }
        Data pre = first;
        Data cur = first.next;
        while(cur!=null){
            if(cur.obj.equals(obj)){
                pre.next = cur.next;
                pre = pre.next;
                cur = pre.next;  //   pre.next          
                continue;   //       ，       
            }
            pre = cur;
            cur = cur.next;
        }
    }
    //    
    public void display()throws Exception{
        if(first == null)
            throw new Exception("your list is empty");
        Data cur = first;
        while(cur!=null){
            System.out.print(cur.obj.toString()+"->");
            cur = cur.next;
        }
        System.out.println();
    }
}

    
1 -> 2 -> 3 -> 4 ->   
2 -> 3 -> 4 ->   
2 -> 4 ->   
null  
4 

양 끝 링크
양 끝 링크 는 양 방향 링크 가 아니 라 양 끝 은 마지막 노드 의 참조 (last) 에 불과 합 니 다.
insert First: 표 머리 에 새로운 노드 를 삽입 합 니 다. 시간 복잡 도 O (1) insert Last: 표 끝 에 새로운 노드 를 삽입 합 니 다. 시간 복잡 도 O (1) deleteFirst: 표 머리의 노드 를 삭제 합 니 다. 시간 복잡 도 O (1) deleteLast: 표 끝의 노드 를 삭제 합 니 다. 표 끝의 노드 만 저장 되 어 있 기 때문에 표 끝의 앞 노드 (단 방향, 뒤로 만 밀 수 있 습 니 다) 를 저장 하지 않 습 니 다.따라서 표 끝 노드 를 삭제 할 때 표 끝 노드 의 앞 노드 를 찾 으 려 면 N - 1 번, 즉 O (N) 를 찾 아야 합 니 다.
2 단 링크 로 대기 열 을 실현 하 다.

public class FirstLastList {
     private class Data{
         private Object obj;
         private Data next = null;
         Data(Object x){
             this.obj = x;
         }
     }

     Data first = null;
     Data last = null;

     public void insertFirst(Object obj){
         Data data = new Data(obj);
         if(first==null)
             last=data;  
         data.next = first;
         first = data;
     }

    public void insertLast(Object obj){
         Data data = new Data(obj);
         if(first==null){
             first = data;
         }else{
            last.next = data;
         }
         last = data;
     }

    public Object deleteFirst()throws Exception{
        if(first==null)
            throw new Exception("empty!");
        Data temp = first;
        if(first.next==null)
            last = null;
        first = first.next;   //if first.next = null that means first = null
        return temp.obj;
    }

    public void deleteLast()throws Exception{
        if(first==null)
            throw new Exception("empty!");
        if(first.next==null){  //single node scenario
            first = null;
            last = null;
        }else{
            Data cur = first;
            while(cur.next!=null){  //stop by end
                if(cur.next==last){
                    last = cur;
                    last.next = null;
                    break;   //  break      ？？                      cur = cur.next
                }
                cur = cur.next;
            }
        }
    }

    public void display()throws Exception{
        if(first == null)
            throw new Exception("your list is empty");
        Data cur = first;
        while(cur!=null){
            System.out.print(cur.obj.toString()+"->");
            cur = cur.next;
        }
        System.out.println();
    }

    public static void main(String[] args) throws Exception {
     FirstLastList fll = new FirstLastList();  
        fll.insertFirst(2);  
        fll.insertFirst(1);  
        fll.display();  
        fll.insertLast(3);  
        fll.display();  
        fll.deleteFirst();  
        fll.display();  
        fll.deleteLast();  
        fll.display();  
    }
}

    
    1 -> 2 ->   
    1 -> 2 -> 3 ->   
    2 -> 3 ->   
    2 ->   

질서 있 는 링크
단 방향 링크 는 삽입 할 때 순 서 를 정할 뿐이다.
표 의 삽입 과 삭 제 는 평균 N/2 회, 즉 O (N) 를 비교 해 야 하지만 최소 데이터 항목 을 얻 으 려 면 O (1) 만 필요 합 니 다. 항상 표 머리 에 있 기 때문에 최소 데이터 항목 을 자주 조작 하 는 응용 은 질서 있 는 링크 를 사용 하여 이 루어 지 는 것 을 고려 할 수 있 습 니 다. 예 를 들 어 우선 순위 대기 열 등 입 니 다.

public class SortedList {
     private class Data{  
            private Object obj;  
            private Data next = null;  

            Data(Object obj){  
                this.obj = obj;  
            }  
        }  

     private Data first = null;

     public void insert(Object obj){
         Data data = new Data(obj);

         Data pre = null;
         Data cur = first;

         while(cur!=null&&Integer.valueOf(data.obj.toString()).intValue()>
         Integer.valueOf(cur.obj.toString()).intValue()){
             pre = cur;
             cur = cur.next;
         }
         if(pre==null)
             first = data;
         else
             pre.next = data;
         data.next = cur;
     }

     public Object deleteFirst()throws Exception{
         if(first==null)
             throw new Exception("empty");
         Data temp = first;
         first = first.next;
         return temp.obj;
     }

     public void display(){
         if(first == null)  
                System.out.println("empty");  
            System.out.print("first -> last : ");  
            Data cur = first;  
            while(cur != null){  
                System.out.print(cur.obj.toString() + " -> ");  
                cur = cur.next;  
            }  
            System.out.print("
");
     }



     public static void main(String[] args) throws Exception{
         SortedList sl = new SortedList();  
            sl.insert(80);  
            sl.insert(2);  
            sl.insert(100);  
            sl.display();  
            System.out.println(sl.deleteFirst());  
            sl.insert(33);  
            sl.display();  
            sl.insert(99);  
            sl.display();  
    }
}

    
first -> last : 2 -> 80 -> 100 -> 
2
first -> last : 33 -> 80 -> 100 -> 
first -> last : 33 -> 80 -> 99 -> 100 ->