[코드트리 조별과제] 연결리스트

연결리스트 구현법 정리하기

connect

1. 시작과 종료를 인자로 받는다.
2. 시작의 다음 = 종료 노드
3. 종료의 이전 = 시작 노드

뒤에 추가

1. 타겟과 삽입 노드를 인자로 받는다.
2. 연결(삽입, 타겟의 다음 노드)
3. 연결(타겟, 삽입)

앞에 추가

1. 타겟과 삽입 노드를 인자로 받는다.
2. 연결(타겟의 이전, 삽입)
3. 연결(삽입, 타겟)

삭제하기

1. 삭제할 노드를 인자로 받는다.
2. 삭제할 노드의 다음 노드의 prev 주소 = 삭제할 노드의 이전 노드
3. 삭제할 노드의 이전 노드의 next 주소 = 삭제할 노드의 다음 노드

연속 노드를 제거하고 특정 노드 뒤에 붙이기

s에서 e까지의 연속한 노드를 리스트에서 제거하고 v 뒤에 추가해보자.

1. s의 이전 노드와 e의 다음 노드를 이어줍니다.
2. s의 이전노드와 e의 다음 노드를 null로 지정합니다.
3. v의 이전노드와 s를 이어줍니다.
4. e와 v를 이어줍니다.

연속 노드끼리 자리 밖구기

1. 각 노드의 이전노드와 다음 노드 상태를 저장합니다.
   1. c의 이전 노드 저장
   2. d의 다음 노드 저장
   3. a의 이전 노드 저장
   4. b의 다음 노드 저장
2. b와 c가 인접한 경우,

예제 풀어보기

배열에서 자리 바꾸기

https://www.codetree.ai/missions/8/problems/switch-position-in-array?&utm_source=clipboard&utm_medium=text

import java.io.*;
import java.util.*; 
class Node{
    int id;
    Node prev, next;

    public Node(int id){
        this.id = id;
        this.prev = null;
        this.next = null; 
    }

    public String toString(){
        return this.id+"";
    }
}

public class Main {
    static BufferedReader buffer = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer tokens;
    static Node[] nodes; 
    public static void main(String[] args) throws IOException{
        int n= Integer.parseInt(buffer.readLine());
        int q = Integer.parseInt(buffer.readLine());

        nodes = new Node[n+1];
        for(int id=1; id<=n; id++){
            nodes[id] = new Node(id); 
        }
        

        for(int id=1; id<n; id++){
            connect(nodes[id], nodes[id+1]); 
        }

        for(int query=0; query<q; query++){
            tokens = new StringTokenizer(buffer.readLine()); 

            int a = Integer.parseInt(tokens.nextToken());
            int b = Integer.parseInt(tokens.nextToken());
            int c = Integer.parseInt(tokens.nextToken());
            int d = Integer.parseInt(tokens.nextToken());

            swap(nodes[a],nodes[b],nodes[c],nodes[d]);
            
        }

        Node cur = nodes[1];


        while(cur.prev!=null){
            cur = cur.prev; 
        }


        StringBuilder result = new StringBuilder(); 
        while(cur.next!=null){
            result.append(cur).append(" ");
            cur = cur.next; 
        }result.append(cur);

        System.out.println(result);
    }

    static void connect(Node s, Node e){
        if(s!=null)s.next = e; 
        if(e!=null)e.prev = s; 
    }

    static void swap(Node a, Node b, Node c, Node d){
        Node afterPrevA = c.prev; 
        Node afterNextB = d.next; 
        Node afterPrevC = a.prev;
        Node afterNextD = b.next; 

        if(b.next==c){
            afterPrevA = d;
            afterNextD = a; 
        }

        if(d.next==a){
            afterNextB = c;
            afterPrevC = b; 
        }

        connect(afterPrevA, a);
        connect(b, afterNextB);

        connect(afterPrevC, c);
        connect(d, afterNextD);
    }
}

테디의 여행 플래너

https://www.codetree.ai/missions/8/problems/teddys-travel-planner?&utm_source=clipboard&utm_medium=text

import java.io.*; 
import java.util.*; 
class Node{
    String city;
    Node prev, next;
    public Node(String city){
        this.city = city;
        this.prev = null;
        this.next = null; 
    }

    public String toString(){
        StringBuilder result = new StringBuilder();

        String prevCity = this.prev!=null? this.prev.city:"-1";
        String nextCity = this.next!=null? this.next.city:"-1";

        if(prevCity.equals(nextCity)||prevCity.equals("-1")||nextCity.equals("-1")){
            return "-1";
        }

        return result.append(prevCity).append(" ").append(nextCity).toString();
    }
}
public class Main {
    static BufferedReader buffer = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer tokens; 


    public static void main(String[] args) throws IOException{
        tokens = new StringTokenizer(buffer.readLine());

        int n = Integer.parseInt(tokens.nextToken());
        int q = Integer.parseInt(tokens.nextToken()); 
        
        Node[] firstCities = new Node[n];
        
        tokens = new StringTokenizer(buffer.readLine());
        for(int i=0; i<n; i++){
            firstCities[i] = new Node(tokens.nextToken());
        }

        Node pinset = new Node("0"); 
        for(int i=0; i<n-1; i++){
            Node s = firstCities[i];
            Node e = firstCities[i+1];
            connect(s,e); 
            if(i==0) pinset = s;
            if(i==n-2)connect(e, pinset); 
        }

        
        StringBuilder result = new StringBuilder(); 

       
        
        for(int query=0; query<q; query++){
            tokens= new StringTokenizer(buffer.readLine());
            int opt=Integer.parseInt(tokens.nextToken()); 
            //result.append(opt).append("\n"); 
            if(opt==1){
                if(pinset.next!=null){
                    pinset = pinset.next; 
                }
            }else if(opt==2){
                if(pinset.prev!=null){
                    pinset = pinset.prev; 
                }
            }else if(opt==3){
                if(pinset.next!=null){
                    remove(pinset.next); 
                }
                
            }else if(opt==4){
                String city= tokens.nextToken();
                insertNext(pinset, new Node(city));
            }
            result.append(pinset).append("\n");
        }   
        System.out.println(result); 


        
    }

    private static void connect(Node s, Node e){
        if(s!=null)s.next = e;
        if(e!=null)e.prev = s; 

    }

    private static void print(Node start){
        while(start.next!=null){
            System.out.print(start.city+" "); 
            start = start.next; 
        }
        System.out.println(start.city);
    }
    private static void insertNext(Node target, Node insert){
        connect(insert, target.next);
        connect(target, insert); 
    }

    private static void remove(Node n){
        if(n.next!=null)n.next.prev = n.prev;
        if(n.prev!=null)n.prev.next = n.next; 
        n.prev = n.next = null; 
    }
}