2. 연결리스트

데이터가 자료의 주소 값으로 서로 연결되어있는 구조

Array vs. Linked List

	Array	Linked List
장점	무작위 접근 가능	빠른 자료의 삽입과 삭제 자유로운 크기 조절
단점	느린 자료 삽입 & 삭제 크기 조절 불가능	순차 접근만 가능 메모리 추가 할당

정적 할당을 사용하여 연결 리스트 구현: 메모리 풀을 통해 정적 할당하기

!메모리 풀의 장점!

1. 동적 할당을 하는 오버헤드가 없어짐

2. 사용이 끝날 때마다 메모리 해제할 필요 없음

3. 모든 노드가 메모리 상에서 뭉쳐 있어서 캐시 효율이 높아짐

(미리 사용될 노트를 할 번에 모두 할당한 다음, 필요할 때마다 하나씩 꺼내 쓰는 방식)

---

구현 연습 - 이중연결리스트

https://www.codetree.ai/missions/8/problems/linked-list1?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

import java.util.*;

class Node {
    String data;
    Node prev, next;

    public Node(String data) {
        this.data = data;
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        String S_init = sc.next();
        int n = sc.nextInt();

        Node initNode = new Node(S_init);
        Node curr = initNode;
        
        for (int i = 0; i < n; i++) {
            int cmd = sc.nextInt();

            if (cmd == 1) { // 이전 노드에 추가
                String S_value = sc.next();
                Node prevNode = new Node(S_value);
                prevNode.next = curr;
                prevNode.prev = curr.prev;
                
                if (curr.prev != null) {
                    curr.prev.next = prevNode;  
                }
                curr.prev = prevNode;
            } else if (cmd == 2) { // 다음 노드에 추가
                String S_value = sc.next();
                Node nextNode = new Node(S_value);
                nextNode.prev = curr;
                nextNode.next = curr.next;

                if (curr.next != null) {
                    curr.next.prev = nextNode;
                }
                curr.next = nextNode;
            } else if (cmd == 3) { // 이전으로 이동
                if (curr.prev != null) {
                    curr = curr.prev;
                }
            } else { // 4: 다음으로 이동
                if (curr.next != null) {
                    curr = curr.next;
                }
            }

            // 현재 상태 출력
            System.out.print((curr.prev == null ? "(Null) " : curr.prev.data + " "));
            System.out.print(curr.data + " ");
            System.out.print((curr.next == null ? "(Null) " : curr.next.data + " "));
            System.out.println();
        }
    }
}

 

---

실습

1. 암호문3

import java.util.LinkedList;
import java.util.Scanner;

public class Solution {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		for (int tc=1; tc<=10; tc++) {
			LinkedList<Integer> lst = new LinkedList<>();
			
			int n = sc.nextInt(); // 암호문의 갯수 
			
			// 원본 암호문 뭉치 
			for (int i=0; i<n; i++) {
				lst.add(sc.nextInt());
			}
			
			int m = sc.nextInt(); // 명령어의 갯수 
			
			// 명령어 
			for (int i=0; i<m; i++) {
				char cmd = sc.next().charAt(0);
				
				if (cmd == 'I') {
					int x = sc.nextInt();
					int y = sc.nextInt();
					
					for (int j=0; j<y; j++) {
						lst.add(x++, sc.nextInt());
					}
				} else if (cmd == 'D') {
					int x = sc.nextInt();
					int y = sc.nextInt();
					
					for (int j=0; j<y; j++) {
						lst.remove(x);
					}
				} else {
					int y = sc.nextInt();
					for (int j=0; j<y; j++) {
						lst.add(sc.nextInt());
					}
				}
			}
			
			System.out.print("#" + tc + " ");
			for (int i=0; i<10; i++) {
				System.out.print(lst.get(i) + " ");
			}
            System.out.println();
		}

	}

}

2. 수열 편집 

package review;

import java.util.LinkedList;
import java.util.Scanner;

public class Solution {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int T = sc.nextInt();
		for (int tc=1; tc<=T; tc++) {
			int n = sc.nextInt(); // 수열의 길
			int m = sc.nextInt(); // 추가 횟
			int l = sc.nextInt(); // 출력할 인덱스 번호 
			
			LinkedList<Integer> lst = new LinkedList<>();
			
			for (int i=0; i<n; i++) {
				lst.add(sc.nextInt());
			}
			
			for (int i=0; i<m; i++) {
				char cmd = sc.next().charAt(0);
				
				int idx = sc.nextInt();
				if (cmd == 'I') {
					int value = sc.nextInt();
					lst.add(idx, value);
				} else if (cmd == 'D') {
					lst.remove(idx);
				} else {
					int value = sc.nextInt();
					lst.set(idx, value);
				}
			}
			
			System.out.print("#" + tc + " ");
			
			if (lst.size() <= l) {
				System.out.println(-1);
			} else {
				System.out.println(lst.get(l));
			}
		}

	}

}