CSE/Data Structure 검색 결과

8개 발견
  1. 미리보기
    2016.04.16 - Palpit

    [Data Structure] 그래프 순회, 탐색(BFS) - 자료 구조

  2. 미리보기
    2016.04.16 - Palpit

    [Data Structure] 그래프 순회, 탐색(DFS) - 자료 구조

  3. 미리보기
    2016.04.10 - Palpit

    [Data Structure] 그래프(Graph) - 자료 구조

  4. 미리보기
    2015.06.12 - Palpit

    [Data Structure] 자료구조 - 큐(Queue)

  5. 미리보기
    2015.06.12 - Palpit

    [Data Structure] 자료구조 - 스택 (Stack)

  6. 미리보기
    2015.06.12 - Palpit

    [Data Structure] 자료구조 - 연결 리스트(Linked List) - 이중 연결 리스트(Double Linked List)

  7. 미리보기
    2015.06.12 - Palpit

    [Data Structure] 자료구조 - 연결 리스트(Linked List) - 원형 연결 리스트(Circular Linked List)

  8. 미리보기
    2015.06.12 - Palpit

    [Data Structure] 자료구조 - 연결 리스트(Linked List) - 단순 연결 리스트(Singly / Linear Linked List)

조회수 확인


그래프 순회(Graph Traversal)



2. 너비 우선 탐색


BFS(Breadth First Search)


시작 정점으로부터 인접한 정점들을 모두 차례로 방문하고 나서

방문했던 정점을 시작으로 다시 인접한 정점들을 차례로 방문하여 가까운 정점들을 번저 방문하는 방법


인접한 정점들에 대해 차례로 다시 너비 우선 탐색을 반복해야 하므로 FIFO 구조를 갖는 Queue를 사용합니다.



너비 우선 탐색 과정 



초기 상태


visited를 초기화하고 공백 큐 생성








1. 정점 A를 시작으로 너비 우선 탐색 시작


visited[A] = true;

A 방문






2. 정점 A에서 방문하지 않은 모든 인접 정점 B, C를 방문하고  큐에 enQueue


visited[B & C] = true;

B & C 방문

enQueue(B & C);








3. 정점 A에 대한 인접 정점들을 처리헀으므로 탐색을 계속할 다음 정점을 찾기 위해 deQueue하여 B를 받음


vertex = deQueue();








4. 정점 B에서 방문하지 않은 모든 인접 정점 D, E를 방문하고 큐에 enQueue


visited[D&E] = true;

D & E 방문

enQueue(D & E);








5. 정점 B에 대한 인접 정점을 처리했으므로 탐색을 계속할 다음 정점을 찾기위해 큐를 deQueue


vertex = deQueue();








6. 정점 C에 방문하지 않은 정점이 없으므로 탐색을 계속할 다음 정점을 찾기 위해 큐를 deQueue


vertex = deQueue();












7. 정점 D에 방문하지 않은 정점 G를 방문하고 큐에 enQueue


visited[G] = true;

G 방문

enQueue(G);








8. 정점 D에 대한 인접 정점들을 처리했으므로 탐색을 계속할 다음 정점을 찾기위해 큐를 deQueue


vertex = deQueue();









9. 정점 E에는 방문하지 않은 인접 정점이 없으므로 탐색을 계속할 다음 정점을 찾기 위해 큐를 deQueue


vertex = deQueue();






10. 정점 G에서 방문하지 않은 인접 정점 F를 방문하고 큐에 enQueue


visited[F] = true;

F 방문

enQueue(F);




11. 정점 G에 대한 인접 정점을 처리했으므로 탐색을 계속할 정점을 찾기 위해 큐를 deQueue


vertex = deQueue();







12. 정점 F는 모든 인접 정점을 방문했으므로 다음 정점을 찾기 위해 deQueue, 하지만 큐가 공백이므로 탐색 종료







링크드 리스트로 표현된 너비 우선 탐색 예제를 봅시다.





 * Graph2.java


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
package ssww;
 
 
public class Graph2 {
    GraphType g;
    
    public Graph2() {
        g = new GraphType();
        g.n = 0;
        
        for (int i = 0; i < g.MAXVERTEX; i++) {
            g.visited[i] = false;
            g.adjList[i] = null;
        }
    }
    
    public void insertVertex(int v) {
        if ((g.n + 1> g.MAXVERTEX) {
            System.out.println("그래프의 정점의 갯수 초과!");
            return;
        }
        
        g.n++;
    }
    
    public void insertEdge(int u, int v) {
        GraphNode node;
        
        if (u >= g.n || v >= g.n) {
            System.out.println("그래프에 없는 정점!");
            return;
        } 
        node = new GraphNode();
        node.vertex = v;
        node.link = g.adjList[u];
        g.adjList[u] = node;
    }
    
    public void printAdjList() {
        GraphNode tmp;
        
        for (int i = 0; i < g.n; i++) {
            System.out.println("\n\t 정점 " + (char)(i + 65+ "의 인접 리스트");
            tmp = g.adjList[i];
            
            while (tmp != null) {
                System.out.print(" -> " + (char) (tmp.vertex + 65));
                tmp = tmp.link;
            }
        }
    }
 
    public void breadthFirstSearch(int v) {
        GraphNode tmp;
        Queue queue = new Queue();
        g.visited[v] = true;
        System.out.print(" " + (char)(v + 65));
        queue.enQueue(v);
        
        while (! queue.isEmpty()) {
            v = queue.deQueue();
            
            for (tmp = g.adjList[v]; tmp != null; tmp = tmp.link) {
                if (!g.visited[tmp.vertex]) {
                    g.visited[tmp.vertex] = true;
                    System.out.print(" " + (char) (tmp.vertex + 65));
                    queue.enQueue(tmp.vertex);
                }
            }
        }
    }
}
 
class QueueNode {
    int data;
    QueueNode link;
    
    public QueueNode(int data) {
        this.data = data;
    }
}
 
class Queue {
    QueueNode front, rear;
    
    public Queue() {
        front = null;
        rear = null;
    }
    
    public boolean isEmpty() {
        if (front == nullreturn true;
        return false;
    }
    
    public void enQueue(int data) {
        QueueNode node = new QueueNode(data);
        node.link = null;
        
        if (front == null) {
            front = node;
            rear = node;
        } else {
            rear.link = node;
            rear = node;
        }
    }
    
    public int deQueue() {
        QueueNode oldNode = front;
        int data;
        
        if (isEmpty()) return 0;
        else {
            data = oldNode.data;
            front = front.link;
            
            if (front == null
                rear = null;
            oldNode = null;
            
            return data;
        }
    }
}
 
 
 
 
cs





 * GraphMain2.java


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
package ssww;
 
 
public class GraphMain2 {
 
    public static void main(String[] args) {
        Graph2 graph = new Graph2();
        
        for (int i = 0; i < 7; i++
            graph.insertVertex(i);
        
        graph.insertEdge(02);
        graph.insertEdge(01);
        graph.insertEdge(14);
        graph.insertEdge(13);
        graph.insertEdge(10);
        graph.insertEdge(24);
        graph.insertEdge(20);
        graph.insertEdge(36);
        graph.insertEdge(31);
        graph.insertEdge(46);
        graph.insertEdge(42);
        graph.insertEdge(41);
        graph.insertEdge(56);
        graph.insertEdge(65);
        graph.insertEdge(64);
        graph.insertEdge(63);
        
        System.out.print("\n 인접 리스트: ");
        graph.printAdjList();
        
        System.out.println("\n너비 우선 탐색: ");
        graph.breadthFirstSearch(0);
    }
 
}
 
 
 
cs




* 클래스 다이어그램










 

end





tags: Data Structure, 그래프, Graph, 자료 구조, 간선, 정점, Vertex, EdgeGraph Traversal, Graph Search, Traverse, 그래프 순회, BFS, BreadthFirstSearch


다른 카테고리의 글 목록

CSE/Data Structure 카테고리의 포스트를 톺아봅니다
조회수 확인

그래프 순회(Graph Traversal)


하나의 정점에서 그래프의 모든 정점을 한 번씩 방문하는 것을 그래프 순회라고 합니다.


탐색 방법에는 


'깊이 우선 탐색(DFS)'


'너비 우선 탐색(BFS)'





1. 깊이 우선 탐색


DFS(Depth First Search)


시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 탐색하다 막히면 

가장 마지막 갈림길 간선이 있는 정점으로 돌아와서 다른 방향의 간선으로 탐색을 계속하는 탐색 방법


이 탐색 방법에서는 스택(Stack)을 이용하여서 탐색합니다.



깊이 우선 탐색 과정



1. 초기 배열 visited를 False로 초기화하고 공백 스택 생성






2. 정점 A를 시작으로 깊이 우선 탐색 시작


visited[A] = true;





3. 정점 A에 방문하지 않은 정점 B, C가 있으므로 A를 스택에 push하고, 인접 정점 B와 C 중 오름차순에 따라 B를 선택하여 탐색


 push(stack, A);

visited[B] = true;






4. 정점 B에 방문하지 않은 정점 D, E가 있으므로 B를 스택에 push하고, D와 E 중 오름차순에 따라 D를 선택하여 탐색


push(stack, B);

visited[D] = true;






5. 정점 D에서 방문하지 않은 정점 G가 있으므로 D를 스택에 push하고, G를 선택하여 탐색


push(stack, D);

visited[G] = true;






6. 정점 G에 방문하지 않은 정점 E, F가 있으므로 G를 스택에 push하고, E와 F 중 오름차순에 따라 E를 선택하여 탐색


push(stack, G);

visited[E] = true;






7. 정점 E에 방문하지 않은 정점 C가 있으므로 E를 스택에 push하고, C를 선택하여 탐색


push(stack, E);

visited[C] = true;









8.  정점 C에 방문하지 않은 인접 정점이 없으므로 스택에서 pop하여 이전 정점에서 방문하지 않은 인접 정점이 있는지 확인


pop(stack);


E의 인접 정점은 B, C, G 인데 배열을 보면 모두 True로 방문 되어 있음.






9. 현재 정점 E에서 방문할 수 있는 인접 정점이 없으므로, 스택을 pop하여 받은 정점 G에 대해 방문하지 않은 인접 정점이 있는지 확인


pop(stack);


G의 인접 정점은 D, E, F 인데 F는 False로 방문하지 않은 것으로 되어 있음






10. 현재 정점 G에서 방문하지 않은 정점 F가 있으므로 G를 스택에 push하고, 정점 F를 선택하여 탐색


push(stack, G);

visited[F] = true;






11. 현재 정점 F에서 방문하지 않은 정점이 없으므로, 스택을 pop하여 받은 정점 G에 대해 방문하지 않은 정점이 있는지 확인


pop(stack);







이와 같은 방법으로 스택을 pop하고 방문확인을 하여 탐색




링크드 리스트로 구현한 DFS 예제를 보도록 합시다.




 * Graph.java

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
package ssww;
 
 
public class Graph {
    
    GraphType g;
    
    public Graph() {
        g = new GraphType();
    }
    
    public void createGraph() {
        g.n = 0;
        
        for (int i = 0; i < g.MAXVERTEX; i++) {
            g.visited[i] = false;
            g.adjList[i] = null;
        }
    }
    
    public void insertVertex(int v) {
        if ((g.n + 1> g.MAXVERTEX) {
            System.out.println("그래프의 정점의 갯수 초과!");
            return;
        }
        
        g.n++;
    }
    
    public void insertEdge(int u, int v) {
        GraphNode node;
        
        if (u >= g.n || v >= g.n) {
            System.out.println("그래프에 없는 정점!");
            return;
        } 
        node = new GraphNode();
        node.vertex = v;
        node.link = g.adjList[u];
        g.adjList[u] = node;
    }
    
    public void printAdjList() {
        GraphNode tmp;
        
        for (int i = 0; i < g.n; i++) {
            System.out.println("\n\t 정점 " + (char)(i + 65+ "의 인접 리스트");
            tmp = g.adjList[i];
            
            while (tmp != null) {
                System.out.print(" -> " + (char) (tmp.vertex + 65));
                tmp = tmp.link;
            }
        }
    }
    
    public void depthFirstSearch(int v) {
        GraphNode tmp;
        Stack stack = new Stack();
        stack.top = null;
        stack.push(v);
        
        g.visited[v] = true;
        System.out.print(" " + (char) (v + 65));
        
        while (stack.top != null) {
            tmp = g.adjList[v];
            
            while (tmp != null) {
                if (!g.visited[tmp.vertex]) {
                    stack.push(tmp.vertex);
                    g.visited[tmp.vertex] = true;
                    System.out.print(" " + (char) (tmp.vertex + 65));
                    v = tmp.vertex;
                    tmp = g.adjList[v];
                } else tmp = tmp.link;
            }
            v = stack.pop();
        }
    }
}
 
class GraphType {
    final int MAXVERTEX = 10;
    
    int n;
    GraphNode adjList[];
    boolean visited[];
    
    public GraphType() {
        adjList = new GraphNode[MAXVERTEX];
        visited = new boolean[MAXVERTEX];
    }
 
}
 
class GraphNode {
    int vertex;
    GraphNode link;
    
}
 
class StackNode {
    int data;
    StackNode link;
    
    public StackNode(int data) {
        this.data = data;
    }
}
 
class Stack {
    StackNode top;
    
    public void push(int data) {
        StackNode tmp = new StackNode(data);
        tmp.link = top;
        top = tmp;
    }
    
    public int pop() {
        int data;
        StackNode tmp = top;
        
        if (top == null) {
            System.out.println("Stack is Empty!!");
            return 0;
        } else {
            data = tmp.data;
            top = tmp.link;
            tmp = null;
            return data;
        }
    }
}
 
 
 
cs





 * GraphMain.java


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
 
 
 
 
 
 
 
 
 
 
 
 
package ssww;
 
public class GraphMain {
    public static void main(String[] args) {
        Graph graph = new Graph();
        graph.createGraph();
        
        for (int i = 0; i < 7; i++
            graph.insertVertex(i);
        
        graph.insertEdge(02);
        graph.insertEdge(01);
        graph.insertEdge(14);
        graph.insertEdge(13);
        graph.insertEdge(10);
        graph.insertEdge(24);
        graph.insertEdge(20);
        graph.insertEdge(36);
        graph.insertEdge(31);
        graph.insertEdge(46);
        graph.insertEdge(42);
        graph.insertEdge(41);
        graph.insertEdge(56);
        graph.insertEdge(65);
        graph.insertEdge(64);
        graph.insertEdge(63);
        
        System.out.print("Graph의 인접 리스트: ");
        graph.printAdjList();
        
        System.out.println("\n\n Depth First Search:");
        graph.depthFirstSearch(0);
    }
}
 
 
 
cs





Class Diagram










end





tags: Data Structure, 그래프, Graph, 자료 구조, 간선, 정점, Vertex, EdgeGraph Traversal, Graph Search, Traverse, 그래프 순회, DFS, DepthFirstSearch


다른 카테고리의 글 목록

CSE/Data Structure 카테고리의 포스트를 톺아봅니다
조회수 확인

그래프(Graph)



개념: 연결되어 있는 원소 간의 관계를 표현하는 자료구조


버스 노선도나 전철 노선도, 인간 관계 인맥 로드맵, 수도 배수 시스템 등 폭 넓게 쓰임.




그래프는 연결할 객체를 나타내는 정점(Vertex)과 

객체를 연결하는 간선(Edge)의 집합으로 구성



'G = (V,E)' 


V 는 그래프에 있는 정점들의 집합

E 는 정점을 연결하는 간선들의 집합











1. 그래프의 종류


무방향 그래프


무방향 그래프(Undirected Graph)는 두 정점을 연결하는 간선의 방향이 없는 그래프입니다. 

무방향 그래프에서 정점 Vi와 정점 Vj을 연결하는 간선을 (Vi, Vj)로 표현하고

(Vi, Vj)와 (Vj, Vi)는 같은 간선을 나타냅니다.


위 그림에서의 그래프는 무방향 그래프입니다. 


왼쪽 그래프를 G1, 오른쪽 그래프를 G2라 했을 때, 아래와 같이 표현 가능합니다.


V(G1) = {A, B, C}     E(G1) = {(A,B), (A,C), (B,C)}

V(G2) = {A, B, C, D}     E(G2) = {(A,B), (B,C), (B,D), (A,C), (C,D)}



방향 그래프


방향 그래프(Directed Graph)는 간선에 방향이 있는 그래프입니다.


방향 그래프에서 정점 Vi와 정점 Vj를 연결하는 간선 Vi -> Vj를 <Vi, Vj>로 표현하고 화살표로 나타냅니다.


Vi를 Tail, Vj를 Head라고 합니다.


<Vi, Vj> 와 <Vj, Vi>는 다른 간선입니다.




완전 그래프


완전 그래프(Complete Graph) 는 각 정점에서 다른 모든 정점을 연결하여 가능한 최대의 간선 수를 가진 그래프입니다. 





부분 그래프


원래의 그래프에서 일부의 정점이나 간선을 제외하여 만든 그래프를 부분 그래프(Sub Graph)라고 합니다.




가중 그래프


정점을 연결하는 간선에 가중치(Weight)를 할당한 그래프를 가중 그래프(Weight Graph)라고 합니다.






간단하게 구현된 그래프 예제입니다.


인접 행렬로 G1과 G2를 나타냅니다.



 * Graph.java


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
package ssww;
 
public class Graph {
    public final int MAX_VERTEX = 30;
    
    int n;
    int [][] adjMatrix;
    
    public Graph() {
        n = 0;
        adjMatrix = new int [MAX_VERTEX][MAX_VERTEX];
        
        for (int i = 0; i < MAX_VERTEX; i++) {
            for (int j = 0; j < MAX_VERTEX; j++) {
                adjMatrix[i][j] = 0;
            }
        }
    }
    
    /*
     * 그래프에 정점을 삽입하는 연산
     */
    public void insertVertex(int v) {
        if ((n + 1> MAX_VERTEX) {
            System.out.println("정점의 갯수 초과!");
            return;
        }
        
        n++;
    }
    
    /*
     * 그래프에 간선 (u, v)를 삽입하는 연
     */
    public void insertEdge(int u, int v) {
        if (u >= n || v >= n) {
            System.out.println("그래프에 없는 정점!");
            return;
        }
        
        adjMatrix[u][v] = 1;
    }
    
    public void printMatrix() {
        for (int i = 0; i < n; i++) {
            System.out.print("\n\t");
            for (int j = 0; j < n; j++) {
                System.out.print(adjMatrix[i][j] + " ");
            }
        }
    }
}
 
 
 
cs




 * GraphMain.java


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
 
 
 
 
 
 
 
 
 
 
 
 
package ssww;
 
public class GraphMain {
    public static void main(String[] args) {
        Graph g1, g2;
        
        g1 = new Graph();
        g2 = new Graph();
        
        for (int i = 0; i < 4; i++) {
            g1.insertVertex(i);
        }
        
        g1.insertEdge(01);
        g1.insertEdge(03);
        g1.insertEdge(10);
        g1.insertEdge(12);
        g1.insertEdge(13);
        g1.insertEdge(21);
        g1.insertEdge(23);
        g1.insertEdge(30);
        g1.insertEdge(31);
        g1.insertEdge(32);
        
        System.out.println("G1의 인접 행렬");
        g1.printMatrix();
        
        System.out.println("\n");
        for (int i = 0; i < 3; i++) {
            g2.insertVertex(i);
        }
        
        g2.insertEdge(01);
        g2.insertEdge(02);
        g2.insertEdge(10);
        g2.insertEdge(12);
        g2.insertEdge(20);
        g2.insertEdge(21);
 
        System.out.println("G2의 인접 행렬");
        g2.printMatrix();
    }
}
 
 
 
cs











end





tags: Data Structure, 그래프, Graph, 자료 구조, 간선, 정점, Vertex, Edge

다른 카테고리의 글 목록

CSE/Data Structure 카테고리의 포스트를 톺아봅니다

[Data Structure] 자료구조 - 큐(Queue)

2015.06.12 16:14 - Palpit
조회수 확인

큐(Queue)




개념: 스택과 마찬가지로 삽입, 삭제의 위치와 방법이 제한되어있는 

유한 순서 리스트(Finite ordered list)지만,

스택과 달리 리스트의 한쪽 끝에서는 삽입 작업이 이루어지고, 

반대쪽 끝에서는 삭제 작업이 이루어져서

삽입된 순서대로 삭제되는

 

선입선출(FIFO: First In First Out)


구조 입니다!




흔한 예로 볼수 있는게 


놀이동산의 놀이기구 기다리는 줄이 있죠.



표로 조금 정리를 해서 


스택과 큐의 연산을 비교해 보도록 하겠습니다!



 

항목

자료구조

삽입연산

삭제연산

연산자

삽입 위치

연산자

삽입 위치

스택

push

top

pop

top

enQueue

rear

deQueue

front





이처럼 큐의 삽입은 rear에서 일어나고


큐의 삭제는 front에서 일어납니다!





아래는 큐의 구조입니다!








위에 보시는 것처럼 front에서 삭제가 일어납니다.

front에는 그럼 가장 먼저 들어간 원소가 있는 거죠.


rear에서는 삽입이 일어나고,

가장 나중에 들어온 원소가 존재합니다!





큐는 컴퓨터의 여러분야에서 발생한 순서대로 문제를 해결해야 하는 경우에 선입 선출 구조인 큐를 사용합니다!!





운영체제에서 실행을 요청한 작업들을 순서대로 처리하기 위해 버퍼 큐프로세스 스케줄링 큐


산업공학등의 분야에서 최적의 시스템을 설계하기 위한 시뮬레이션에서 대기 행렬 큐






그럼 예제를 통해 알아보도록 합시다!




먼저, 배열로 구현한 큐의 구조입니다!


클래스다이어그램 먼저 보시죠~








큐에는 크게 4개의 연산을 가지고 있습니다!


enQueue: 큐안에 데이터를 집어 넣는 연산


 deQueue: 큐안의 데이터를 끄집어 내는 연산


Peek: 큐의 front 데이터를 반환하는 연산(deQueue와는 다른 용도입니다!!!)


 Empty: 스택이 비어있는지 불리언 값 반환하는 연산








Quque.java



 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
package queue;
 
public interface Queue {
    public boolean isEmpty();
 
    public void enQueue(String item);
 
    public String deQueue();
 
    public void delete();
 
    public String peek();
}
 
cs





ArrayQueue.java



 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
 
package queue;
 
public class ArrayQueue implements Queue {
 
    private int front;
    private int rear;
    private int queueSize;
    private String[] itemArray;
 
    public ArrayQueue(int queueSize) {
        front = -1;
        rear = -1;
        // 초기의 front와 rear는 같은 위치선상에 있음
 
        this.queueSize = queueSize;
        itemArray = new String[this.queueSize];
    }
 
    public boolean isEmpty() {
        return (front == rear);
    }
 
    public boolean isFull() {
        return (rear == this.queueSize - 1);
    }
 
    public void enQueue(String item) {
        if (isFull()) {
            System.out.println("삽입 실패! 큐가 꽉찼습니다!");
        } else {
            itemArray[++rear] = item;
            System.out.println("삽입된 아이템 : " + item);
        }
    }
 
    public String deQueue() {
        if (isEmpty()) {
            System.out.println("삭제 실패! 큐가 비어있습니다!");
            return null;
        } else {
            return itemArray[++front];
        }
    }
 
    public void delete() {
        if (isEmpty()) {
            System.out.println("삭제 실패! 큐가 비어있습니다!");
        } else {
            ++front;
        }
    }
 
    public String peek() {
        if (isEmpty()) {
            System.out.println("삭제 실패! 큐가 비어있습니다!");
            return null;
        } else {
            return itemArray[front + 1];
        }
    }
 
    public void printQueue() {
        if (isEmpty()) {
            System.out.println("큐가 비어있습니다!");
        } else {
            System.out.print("큐 >> ");
 
            for (int i = front + 1; i <= rear; i++)
                System.out.print(itemArray[i] + " ");
            System.out.println();
        }
    }
 
}
 
cs




QueueMain.java





 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
package queue;
 
public class QueueMain {
    public static void main(String[] args) {
        int queueSize = 4;
        ArrayQueue Q = new ArrayQueue(queueSize);
 
        Q.enQueue("I");
        Q.enQueue("AM");
        Q.enQueue("A");
        Q.enQueue("BOY");
 
        Q.printQueue();
 
        String deleteItem = Q.deQueue();
        if (!deleteItem.isEmpty())
            System.out.println("deleted Item : " + deleteItem);
 
        Q.printQueue();
    }
}
 
cs



결과는 아래와 같습니다!!







 




다음은 원형 큐(Circular Queue)에 대해 진행합니다!!







원형 큐(Circular Queue)



위에서 설명한 기존 큐의 문제는 


프론트와 리어가 붙어있는 경우에 포화상태로 잘못 인식하여 


잘못된 연산을 수행합니다!!


아래와 같은 상황에 말이죠!












위와 같은 상황시에 원소들을 배열의 앞부분으로 이동시켜서 위치를 조정해야합니다!!






그러나!




그렇게 하기엔 이동 작업은 연산이 복잡하고,


큐의 효율성을 떨어트립니다!!!



그래서 고안한게 






원형 큐!!!!






원형 큐는 Circular Linked List의 개념과 비슷하다고 보시면 됩니다!!!




원형 큐의 개념: 



초기 공백 상태일 때 front와 rear의 값이 0 이 되고,



공백 상태와 포화 상태를 쉽게 구분하기 위해서 자리 하나를 항상 비워둡니다!!! 


원형큐에서의 공백상태 조건은 front = rear 와같은 조건이면 공백상태로 인지합니다!!







그럼 소스코드로 보시기 전에 원형큐의 구조를 보시겠습니다!!!











위처럼 돌돌 말려진 큐라고 보시면 되겠습니다!!!



그럼 원형 큐에 대한 알고리즘을 살펴보도록 하죠~





생성 알고리즘




 

1
2
3
4
5
6
7
 
 
createQueue() {
    cQ[n];
    front <- 0;
    rear <- 0;
}
cs




  

공백 검사 & 포화 상태 검사 알고리즘



 

1
2
3
4
5
6
7
8
9
10
isEmpty(cQ) {
    if (front == rear) then return true;
    else return false;
}
 
isFull(cQ) {
    if (((rear + 1) mod n) == front) then return true;
    else return false;
}
 
cs






포화 검사(isFull)이 좀 특이하죠??

rear가 원형 큐를 한바퀴 돌면서 원소를 삽입하여 큐를 모두 채우면 

rear의 다음 위치((rear+1) mod n)는 현재의 front 위치가 되어 

더이상 삽입할 수 없는 포화상태가 됩니다!!! 




삽입 알고리즘



 

1
2
3
4
5
6
7
8
 
enQueue(cQ, item) {
    if(isFull(cQ)) then Queue_Full();
    else {
        rear <- (rear + 1) mod n;
        cQ[rear] <- item;
    }
}
cs





삭제 알고리즘


 

1
2
3
4
5
6
7
deQueue(cQ) {
    if(isEmpty(cQ)) then Queue_Empty();
    else {
        front <- (front + 1) mod n;
        return cQ[front];
    }
}
cs





자 알고리즘은 이정도로 올려 드리고,

소스를 통해서 보겠습니다!!

배열로 구현한 원형 큐 예제입니다!







ArrayCQueue.java



 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
package circularQueue;
 
import queue.Queue;
 
public class ArrayCQueue implements Queue {
    private int front;
    private int rear;
    private int queueSize;
    private String[] itemArray;
 
    public ArrayCQueue(int queueSize) {
        rear = front = 0;
        this.queueSize = queueSize;
        itemArray = new String[this.queueSize];
    }
 
    public boolean isEmpty() {
        return (front == rear);
    }
 
    public boolean isFull() {
        return (((rear + 1) % this.queueSize) == front);
    }
 
    public void enQueue(String item) {
        if (isFull()) {
            System.out.println("삽입 실패! 원형 큐가 꽉찼습니다!");
        } else {
            rear = (rear + 1) % queueSize;
            itemArray[rear] = item;
            System.out.println("삽입된 아이템 : " + item);
        }
    }
 
    public String deQueue() {
        if (isEmpty()) {
            System.out.println("삭제 실패! 원형 큐가 비어있습니다!");
            return null;
        } else {
            front = (front + 1) % queueSize;
            return itemArray[front];
        }
    }
 
    public void delete() {
        if (isEmpty()) {
            System.out.println("삭제 실패! 원형 큐가 비어있습니다!");
        } else {
            front = (front + 1) % queueSize;
        }
    }
 
    public String peek() {
        if (isEmpty()) {
            System.out.println("삭제 실패! 원형 큐가 비어있습니다!");
            return null;
        } else {
            return itemArray[(front + 1) % queueSize];
        }
    }
 
    public void printQueue() {
        if (isEmpty()) {
            System.out.println("원형 큐가 비어있습니다!");
        } else {
            System.out.print(" 원 형  큐 >> ");
 
            for (int i = (front + 1) % queueSize; i != (rear + 1) % queueSize; i = ++i
                    % queueSize)
                System.out.print(itemArray[i] + " ");
            System.out.println();
        }
    }
}
 
cs





QueueMain.java




 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
package circularQueue;
 
public class QueueMain {
    public static void main(String[] args) {
        int queueSize = 5;
 
        ArrayCQueue cQ = new ArrayCQueue(queueSize);
 
        cQ.enQueue("HELLO");
        cQ.enQueue("WORLD");
        cQ.printQueue();
 
        cQ.delete();
        cQ.enQueue("MAP");
        cQ.printQueue();
 
    }
}
 
cs






결과는 아래와 같습니다!!



 




이번 예제의 queue 인터페이스는 이전에 작성한 걸로 끌어다 썼습니다!!!












연결 큐(Linked Queue)


배열로 구현하면 배열의 고질적 문제를 가지고 있게 되죠???


그럼 연결 리스트로 예제를 작성해 보도록 하겠씁니다!






QNode.java
 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
package linkedQueue;
 
public class QNode {
    private String data;
    private QNode link;
 
    public String getData() {
        return data;
    }
 
    public void setData(String data) {
        this.data = data;
    }
 
    public QNode getLink() {
        return link;
    }
 
    public void setLink(QNode link) {
        this.link = link;
    }
 
}
 
cs




LinkedQueue.java



 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
 
package linkedQueue;
 
import queue.Queue;
 
public class LinkedQueue implements Queue {
 
    private QNode front;
    private QNode rear;
 
    public LinkedQueue() {
        front = null;
        rear = null;
    }
 
    public boolean isEmpty() {
        return (front == null);
    }
 
    public void enQueue(String item) {
        QNode newNode = new QNode();
        newNode.setData(item);
        newNode.setLink(null);
 
        if (isEmpty()) {
            front = newNode;
            rear = newNode;
        } else {
            rear.setLink(newNode);
            rear = newNode;
        }
        System.out.println("Inserted Item : " + item);
    }
 
    public String deQueue() {
        if (isEmpty()) {
            System.out.println("Deleting fail!! Linked Queue is empty!");
            return null;
        } else {
            String item = front.getData();
            front = front.getLink();
 
            if (front == null) {
                rear = null;
            }
 
            return item;
        }
 
    }
 
    public void delete() {
        if (isEmpty()) {
            System.out.println("Deleting fail!! Linked Queue is empty!");
        } else {
            front = front.getLink();
            if (front == null) {
                rear = null;
            }
        }
    }
 
    public String peek() {
        if (isEmpty()) {
            System.out.println("Peeking fail!! Linked Queue is empty!");
            return null;
        } else {
            return front.getData();
        }
    }
 
    public void printQueue() {
        if (isEmpty()) {
            System.out.println("Linked Queue is empty!");
        } else {
            QNode tmp = front;
            System.out.print("Linked Queue >> ");
 
            while (tmp != null) {
                System.out.print(tmp.getData() + " ");
                tmp = tmp.getLink();
            }
 
            System.out.println();
        }
    }
 
}
 
cs




QueueMain.java


 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
package linkedQueue;
 
public class QueueMain {
    public static void main(String[] args) {
        LinkedQueue lQ = new LinkedQueue();
 
        lQ.enQueue("THIS");
        lQ.enQueue("IS");
        lQ.enQueue("AWESOME");
        lQ.enQueue("!!");
        lQ.printQueue();
 
        System.out.println();
        System.out.println("삭제 후 출력한 큐");
 
        lQ.delete();
        lQ.delete();
        lQ.printQueue();
    }
}
 
cs




결과는 아래와 같습니다!!!





 


다른 카테고리의 글 목록

CSE/Data Structure 카테고리의 포스트를 톺아봅니다
조회수 확인

스택(Stack)




개념: 스택은 같은 구조와 크기의 자료를 top 이라고 정한 한 곳에만 쌓을 수 있고, 

top으로만 접근하도록 제한하여 만든 자료구조




스택에서 top을 통해 들어온 자료가 일정한 방향으로 차곡차곡 쌓입니다.


마치 뷔페식당의 쌓인 접시나


책상위에 차곡차곡 쌓아 둔 책


과 같이 말이죠~



스택에서 자료를 삭제할 때도 top을 통해서만 가능하기 떄문에 


top이 가리키고 있는 스택의 마지막 자료만 삭제할 수 있습니다.


따라서, 스택은 시간순서에 따라 자료가 쌓이고, 


삭제할 때는 가장 마지막에 삽입된 자료가 가장 먼저 삭제되는 


후입선출(LIFO: Last In First Out)의 구조를 갖습니다.



스택의 구조






 




위처럼 data1,2,3이 차곡차곡 쌓이고 stack에서 top의 위치는 data 3을 가리키는 겁니다!


절대로 스택에서 data3이 먼저 제거되지 않는 한, data2와 data1을 꺼낼수 없습니다!!!




자 그럼 소스 코드를 통해 스택에 대해 알아보도록 합시다!




먼저 


순차 자료구조(배열)로 구현한 스택을 살펴보겠습니다!!!



클래스다이어그램으로 먼저 프리뷰하죠~




 


스택은 크게 4개의 연산을 가지고 있습니다!


Push: 스택안에 데이터를 집어 넣는 연산


Pop: 스택안의 데이터를 끄집어 내는 연산


Top: 스택의 상위 데이터를 반환하는 연산(Pop과는 다른 용도입니다!!!)


Empty: 스택이 비어있는지 불리언 값 반환하는 연산





그럼 소스코드를 보시지요~



stack.java

 

1
2
3
4
5
6
7
8
9
10
package Stack;
 
public interface Stack {
    public boolean isEmpty();
    public void push(String item);
    public String pop();
    public void delete();
    public String top();
}
 
cs



ArrayStack.java


 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
 
package Stack;
 
public class ArrayStack implements Stack {
    private int top;
    private int stackSize;
    private String[] itemArray;
 
    public ArrayStack(int stackSize) {
        this.top = -1;
        this.stackSize = stackSize;
        itemArray = new String[this.stackSize];
    }
 
    public boolean isEmpty() {
        return (top == -1);
    }
 
    public boolean isFull() {
        return (top == this.stackSize - 1);
    }
 
    public void push(String item) {
        if (isFull()) {
            System.out.println("Stack is Overflow!");
        } else {
            itemArray[++top] = item;
            ;
            System.out.println("Inserted Item : " + item);
        }
    }
 
    public String pop() {
        if (isEmpty()) {
            System.out.println("Stack is Underflow!");
            return null;
        } else {
            return itemArray[top--];
        }
    }
 
    public void delete() {
        if (isEmpty()) {
            System.out.println("Deleting fail! Stack is Empty!");
        } else {
            top--;
        }
    }
 
    public String top() {
        if (isEmpty()) {
            System.out.println("top fail! stack is Empty!");
            return null;
        } else {
            return itemArray[top];
        }
    }
 
    public void printStack() {
        if (isEmpty()) {
            System.out.println("Stack is empty!");
        } else {
            System.out.print("Array Stack >> ");
            for (int i = 0; i <= top; i++) {
                System.out.print(itemArray[i] + " ");
            }
            System.out.println();
        }
    }
}
 
cs



StackMain.java


 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
 
package Stack;
 
public class StackMain {
    public static void main(String[] args) {
        int stackSize = 5;
        String deleteItem = null;
        ArrayStack stack = new ArrayStack(stackSize);
 
        stack.push("S");
        stack.printStack();
 
        stack.push("T");
        stack.push("A");
        stack.push("C");
        stack.push("K");
        stack.printStack();
 
        deleteItem = stack.pop();
 
        if (!deleteItem.isEmpty()) {
            System.out.println("deleted Item: " + deleteItem);
        }
 
        stack.printStack();
    }
}
 
cs




결과는 아래와 같습니다!!




 





다음은!


연결 자료구조(배열)로 구현한 스택

을 구현해보겠습니다!



클래스다이어그램부터 보시자.




 




Stack Interface는 위에서 만든 거 고대로 썼어요~



StackNode.java


 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
 
package Stack;
 
public class StackNode {
    private String data;
    private StackNode link;
 
    public StackNode() {
        this.data = "";
        this.link = null;
    }
 
    public StackNode(String data) {
        this.data = data;
        this.link = null;
    }
 
    public StackNode(String data, StackNode link) {
        this.data = data;
        this.link = link;
    }
 
    public String getData() {
        return data;
    }
 
    public void setData(String data) {
        this.data = data;
    }
 
    public StackNode getLink() {
        return link;
    }
 
    public void setLink(StackNode link) {
        this.link = link;
    }
}
 
cs






LinkedStack.java


 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
 
package Stack;
 
public class LinkedStack implements Stack {
    private StackNode top;
 
    public boolean isEmpty() {
        return (top == null);
    }
 
    public void push(String item) {
        StackNode newNode = new StackNode(item, top);
        top = newNode;
        System.out.println("Inserted data: " + item);
    }
 
    public String pop() {
        if (isEmpty()) {
            System.out.println("Stack is Empty!!! ");
            return null;
        } else {
            String item = top.getData();
            top = top.getLink();
            return item;
        }
    }
 
    public void delete() {
        if (isEmpty()) {
            System.out.println("Stack is Empty!!! ");
        } else {
            top = top.getLink();
        }
    }
 
    public String top() {
        if (isEmpty()) {
            System.out.println("Stack is Empty!!");
            return null;
        } else {
            return top.getData();
        }
    }
 
    public void printStack() {
        if (isEmpty()) {
            System.out.println("Stack is Empty!!");
        } else {
            StackNode tmp = top;
            System.out.println("Linked Stack >> ");
            while (tmp != null) {
                System.out.print("  " + tmp.getData() + "   ");
                tmp = tmp.getLink();
            }
            System.out.println();
        }
    }
 
}
 
cs






StackMain.java


 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 
package Stack;
 
public class StackMain {
    public static void main(String[] args) {
        String deleteItem = null;
        LinkedStack lStack = new LinkedStack();
 
        lStack.push("I");
        lStack.push("AM");
        lStack.push("A");
        lStack.push("BOY");
 
        lStack.printStack();
 
        deleteItem = lStack.pop();
        if (!deleteItem.isEmpty()) {
            System.out.println("deleted Item : " + deleteItem);
        }
 
        lStack.printStack();
 
    }
}
 
cs




결과 화면은 아래와 같습니다!!!



 




다른 카테고리의 글 목록

CSE/Data Structure 카테고리의 포스트를 톺아봅니다
조회수 확인

3. 이중 연결 리스트





이번에는 이중 연결 리스트에 대해 포스팅을 진행해 보도록 하겠습니다!!!



개념: 노드에 두 개의 링크 필드와 한 개의 데이터 필드로 구성된 연결리스트 입니다!!



그림으로 삽입, 삭제 연산을 먼저 짚고 넘어가죠!!!




다시 등장한 우리의 진짜 사나이들!!!




이제는 서병장, 호주 물개, 선착수로를 못 본다는게 슬프네요 ㅠㅠ








자 이렇게 서로 서로 참조를 하고 있는 구조가 이중 연결 리스트 입니다.





삽입 연산






여기서 수로형님이 샘과 헨리의 중간에 삽입이 된다고 보죠!!








이렇게 들어갔습니다!!!


그럼 링크에 대해 수정이 좀 가해지겠죠???






먼저 


김수로의 왼쪽 참조를 샘으로 설정!!!







그러고나서 김수로의 오른쪽 참조를 헨리로 설정!!!






 



그리고 샘의 오른쪽 참조를 김수로로 설정하고

헨리의 왼쪽 참조를 김수로로 설정합니다!!!






이렇게 해서 삽입이 끝났네요~~







삭제 연산




자 이번에는 호주 물개가 빠집니다~



보시죠~






 



먼저 이렇게 경석의 오른쪽 참조가 수로를 참조하게되고

수로의 왼쪽 참조가 경석을 참조하게 합니다!!



그렇게 하고 샘을 빼주면 되요!!!




 



 



이렇게 하면 삭제 연산이 끝이 납니다!!!!




자 바로 소스 코드를 통해 확인해 보겠습니다!!!


DblNode.java




 


 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
 
package doubleLink;
 
public class DblNode {
    private DblNode lLink;
    private String data;
    private DblNode rLink;
 
    public DblNode() {
        this.lLink = null;
        this.data = null;
        this.rLink = null;
    }
 
    public DblNode(String data) {
        this.lLink = null;
        this.data = data;
        this.rLink = null;
    }
 
    public DblNode getlLink() {
        return lLink;
    }
 
    public void setlLink(DblNode lLink) {
        this.lLink = lLink;
    }
 
    public String getData() {
        return data;
    }
 
    public void setData(String data) {
        this.data = data;
    }
 
    public DblNode getrLink() {
        return rLink;
    }
 
    public void setrLink(DblNode rLink) {
        this.rLink = rLink;
    }
 
}
 
cs



DoubleLinkedList.java


 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
 
package doubleLink;
 
public class DoubleLinkedList {
    private DblNode head;
 
    public DoubleLinkedList() {
        head = null;
    }
 
    public void insertFirstNode(String data) {
        DblNode newNode = new DblNode(data);
        DblNode tmp;
        if (head == null) {
            this.head = newNode;
        } else {
            tmp = head;
            tmp.setlLink(newNode);
            newNode.setrLink(tmp);
            head = newNode;
        }
    }
 
    public void insertMiddleNode(DblNode pre, String data) {
        DblNode newNode = new DblNode(data);
        DblNode post = pre.getrLink();
        if (post == null) { // 삽입할 노드가 마지막일 경우
            pre.setrLink(newNode);
            newNode.setlLink(pre);
        } else { // 삽입할 노드 뒤에 노드가 있는 경우
            newNode.setlLink(post.getlLink()); // 삽입할 노드의 왼쪽링크를 post의 왼쪽링크
            newNode.setrLink(pre.getrLink()); // 삽입할 노드의 오른쪽링크를 pre의 오른쪽 링크
            pre.setrLink(newNode); // 삽입할 노드의 이전 노드의 오른쪽 링크를 삽입할 노드로
            post.setlLink(newNode); // 삽입할 노드의 이후 노드의 왼쪽 링크를 삽입할 노드로
        }
    }
 
    public void insertLastNode(String data) {
        DblNode newNode = new DblNode(data);
        DblNode tmp = this.head;
 
        if (tmp == null) {
            this.head = newNode;
        } else {
            while (tmp.getrLink() != null) {
                tmp = tmp.getrLink();
            }
            tmp.setrLink(newNode);
        }
    }
 
    public void deleteNode(DblNode pre) {
        if (head == null) {
            System.out.println("리스트가 비어있습니다!");
            return;
        } else {
 
            DblNode old = pre.getrLink();
            if (old == null) {
                return;
            }
 
            DblNode post = old.getrLink();
 
            // 뒤에 노드있으면 서로 연결
            if (post != null) {
                pre.setrLink(post);
                post.setlLink(pre);
            } else { // 뒤에 노드가 없으면 링크 제거
                pre.setrLink(null);
            }
        }
    }
 
    public void deleteLastNode() {
        DblNode pre = this.head;
        DblNode tmp;
        if (head == null) {
            System.out.println("리스트가 비어있습니다!!");
            return;
        } else {
            tmp = head.getrLink();
 
            while (tmp.getrLink() != null) {
                pre = tmp;
                tmp = tmp.getrLink();
            }
 
            pre.setrLink(null);
        }
    }
 
    public DblNode searchNode(String data) {
        DblNode tmp = this.head;
 
        while (tmp != null) {
            if (data == tmp.getData()) {
                return tmp;
            } else {
                tmp = tmp.getrLink();
            }
        }
 
        return tmp;
    }
 
    public void printList() {
        DblNode tmp = this.head;
 
        System.out.print("DL = (");
 
        while (tmp != null) {
            System.out.print(tmp.getData());
            tmp = tmp.getrLink();
            if (tmp != null) {
                System.out.print(", ");
            }
        }
 
        System.out.println(")");
    }
 
}
 
cs




DoubleMain.java


 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
 
package doubleLink;
 
public class DoubleMain {
    public static void main(String[] args) {
        DoubleLinkedList DL = new DoubleLinkedList();
 
        System.out.println("(1) 삽입 연산 수행");
        DL.insertFirstNode("화");
        DL.insertFirstNode("월");
        DL.insertLastNode("목");
        DblNode pre = DL.searchNode("화");
        DL.insertMiddleNode(pre, "수");
        DL.printList();
 
        System.out.println("(2) 마지막 노드 삭제 연산 수행");
        DL.deleteLastNode();
        DL.printList();
 
        System.out.println("(3) 중간 노드 삭제 연산 수행");
        pre = DL.searchNode("월");
        DL.deleteNode(pre);
        DL.printList();
    }
}
 
cs




결과는 아래와 같습니다!!



 








다른 카테고리의 글 목록

CSE/Data Structure 카테고리의 포스트를 톺아봅니다
조회수 확인
a

2. 환영 연결 리스트



자 2번째는 환영 연결 리스트(Circular Linked List) 입니다!




개념: 단순 연결 리스트에서 마지막 노드가 리스트의 첫 번째 노드(Head)를 

가리키게 하여 리스트의 구조를 원형으로 만든 연결 리스트





그림을 통해서 먼저 삽입, 삭제 연산을 알아보도록합시다!





이번에도 진짜사나이 친구들이 나옵니다!




삽입 연산




 



단순 연결 리스트랑 다르게 


형식이도 다음 사람의 이름을 가지고 있는 겁니다!


이젠 기차가 아니라


강강 수월래 라고 할수 있겟죠??



저렇게 셋이서 강강 수월래~


하고 있는데!!



헨리가 이번에도 끼어서 하고 싶다네요~


그래서 샘과 형식 사이에 끼려고 합니다!!!





 



이렇게 말이죠~



아 그럼 어떻게 해야 할까요????


헨리가 샘과 형식 중간에 끼어들었군요.



그러면 서로 참조하는 값을 바꿔줘야 겠죠???



1) 샘은 헨리가 뒤에 있다는걸 알아야하고!


2) 헨리는 뒤에 형식이 있다는 걸 알아야 합니다!!!






1) 부터 풀어보면. 아래처럼 샘이 헨리를 참조하게 되겠죠??



 




2)을 풀어보면.

아래와 같이 될겁니다!!!





 



자 이렇게 해서 삽입 연산이 이루어 집니다!!!




중간에 끼어드는 알고리즘은 아래와 같습니다!


 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
/*
    * CL: 연결 리스트
    * pre: 앞 노드
    * x: 입력할 데이터 값
*/
insertMiddleNode(CL, pre, x) {
    new <- getNode();
    new.data <- x;
    
    if (CL == NULL) then {
        CL <- new;
        new.link <- null;
    } else {
        new.link <- pre.link;
        pre.link <- new;
    }
}
 
cs










삭제 연산


이번에는 형식이가 하차 한다고 하더군요.



한번 해봅시다!




 


헨리가 아직 형식이를 가리키고 있습니다... 


형식이는 하차를 할것이기 때문에.


인수인계(?)로 헨리에게 


자신이 참조한 값을 넘겨줍니다!






 



위와 같이 넘겨주고선, 형식이는 이제 ByeBye~


moon_and_james-45 






 


위와 같이 형식이 삭제되고 헨리가 참조하는 값을 경석 으로 바꿨습니다!




자 알고리즘으로 한번 보시겠습니다!!


 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
/*
    * CL: 연결 리스트
    * pre: 삭제 할 노드의 앞 노드
*/
deleteNode(CL, pre) {
    if (CL == NULL) then error;
    else {
        old <- pre.link;
        pre.link <- old.link;
        if (old == CL) then 
            CL <- old.link;
        free old;
    }
}
cs





자 그럼, 간단한 예제를 통해 접해보도록 하죠!!!



클래스 다이어 그램부터 보시죠~




 




CircuitLinkedList.java


 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
package circuit;
 
import single.ListNode;
 
public class CircuitLinkedList {
    private ListNode head;
 
    public CircuitLinkedList() {
        head = null;
    }
 
    public void insertFirstNode(String data) {
        ListNode newNode = new ListNode(data);
        ListNode tmp;
        if (head == null) {
            head = newNode;
            head.setLink(head); // 환형 연결 리스트 이므로 초기에 자기자신 참조
        } else {
            tmp = head;
            while (tmp.getLink() != head) {
                tmp = tmp.getLink();
            } // 다음 링크가 head이면
 
            newNode.setLink(tmp.getLink());
            tmp.setLink(newNode);
            head = newNode;
        }
    }
 
    // 중간 노드 삽입
    public void insertMiddleNode(ListNode pre, String data) {
        if (pre == null) {
            return;
        }
        ListNode newNode = new ListNode(data);
 
        if (head == null) {
            head = newNode;
            newNode.setLink(newNode);
        } else {
            newNode.setLink(pre.getLink());
            pre.setLink(newNode);
        }
    }
 
    // 마지막 노드에 삽입
    public void insertLastNode(String data) {
        ListNode newNode = new ListNode(data);
 
        // 리스트가 비어있으면 헤드로 지정
        if (head == null) {
            this.head = newNode;
            head.setLink(head);
        } else {
            ListNode tmp = head;
            while (tmp.getLink() != head) {
                // 마지막 원소일때까지 탐색
                tmp = tmp.getLink();
            }
            tmp.setLink(newNode);
            newNode.setLink(head);
        }
    }
 
    public void deleteNode(ListNode pre) {
        if (head == null) {
            System.out.println("리스트가 비어있습니다!");
            return;
        } else {
            ListNode old = pre.getLink();
            pre.setLink(old.getLink());
            if (old == head)
                head = old.getLink();
        }
    }
 
    public void deleteLastNode() {
        ListNode pre, tmp;
 
        if (head == null) {
            System.out.println("리스트가 비어있습니다!");
            return;
        }
 
        if (head.getLink() == head) {
            head = null;
        } else {
            pre = head;
            tmp = head.getLink();
 
            // 마지막 노드의 이전 노드의 링크가 널인 값인지 까지 탐색
            while (tmp.getLink() != head) {
                pre = tmp;
                tmp = tmp.getLink();
            }
 
            pre.setLink(head);
        }
    }
 
    public ListNode searchNode(String data) {
        ListNode tmp = this.head;
 
        while (tmp != null) {
            if (data == tmp.getData())
                return tmp;
            if (tmp.getLink() == head) {
                System.out.println("찾고자 하는 데이터 " + data + "가 없습니다.");
                return null;
            }
 
            tmp = tmp.getLink();
        }
 
        return tmp;
    }
 
    public void printList() {
        ListNode tmp = this.head;
        System.out.print("L = (");
 
        while (tmp != null) {
            System.out.print(tmp.getData());
            tmp = tmp.getLink();
            if (tmp == head)
                break;
            if (tmp != null) {
                System.out.print(", ");
            }
        }
 
        System.out.println(")");
    }
 
}
 
cs



CircuitMain.java


 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 
package circuit;
 
import single.ListNode;
 
public class CircuitMain {
    public static void main(String[] args) {
        CircuitLinkedList CL = new CircuitLinkedList();
        
        System.out.println("(1) 삽입 연산 수행하기");
        CL.insertFirstNode("월");
        ListNode pre = CL.searchNode("월");
        CL.insertMiddleNode(pre, "화");
        CL.insertLastNode("수");
        CL.insertLastNode("목");
        CL.printList();
        
        System.out.println("(2) 삭제 연산 수행하기");
        pre = CL.searchNode("월");
        CL.deleteNode(pre);
        CL.deleteLastNode();
        CL.printList();
    }
}
 
cs



결과는 아래와 같습니다!!


 





다른 카테고리의 글 목록

CSE/Data Structure 카테고리의 포스트를 톺아봅니다
조회수 확인

1. 연결 자료구조




개념: 순차 선형 리스트(배열)는 논리적인 순서와 물리적인 순서가 같기 때문에

원소의 위치를 찾아 액세스하기 쉽다는 장점이 있지만,


삽입 연산이나 삭제 연산에 


원소들을 이동시키는 추가적인 작업과 시간이 필요함.


원소의 개수가 많고, 삽입, 삭제 연산이 많이 발생하는 경우에는

 원소들의 이동 작업으로 인한 오버헤드가 증가함.


결국, 메모리 사용의 비효율성의 문제를 갖음.




이로 인한 문제를 개선한게 바로 


연결 자료구조!!!



각 원소에 저장되어 있는 다음 원소의 주소에 대한 참조에 의해서

연결되는 방식!


효율적으로 메모리 사용을 할 수 있다!



종류: 

단순 연결 리스트, 원형 연결 리스트, 이중 연결 리스트, 이중 원형 연결 리스트





1-1. 노드


개념: 연결 자료구조 방식에서 원소는 연결될 다음 원소에 대한 주소를 저장해야 하기 때문에,


<원소, 주소>


단위로 저장해야 함.


이러한 단위 구조를 노드라 한다!!



노드는 아래 그림과 같이 구성되어 있습니다!







 




 



원소의 값을 저장하는 데이터 필드(Data Field)


다음 노드의 주소를 저장하는 링크 필드(Link Field)








2. 단순 연결 리스트(Singly Linked List)


노드가 하나의 링크 필드에 의해서

다음 노드와 연결되는 구조를 가진 연결 리스트





2-1. 삽입 연산



자 보기 쉽게 설명을 해드리겠습니다!!



진짜사나이들이 기차놀이를 한다고 가정합시다~



 


위처럼 서경석은 샘의 이름을 알고있고,


샘은 형식의 이름을 알고있습니다.


서로 연결되어있는거죠~ 


기차처럼!!





근데 갑자기 헨리가 같이 하고 싶다고 


서경석과 샘의 사이로 끼어 드는 거죠!!!




 




사이로 끼어 드려고 하는 헨리 때문에...



서경석 뒤에는 헨리가 들어오고


헨리 뒤가 샘이겠네요??






그럼 먼저 헨리가 서경석이 가지고 있던 샘의 이름을 넘겨 받습니다!



아래처럼~






그리고 서경석은 뒤에 헨리가 있다는 것을 가지고 있어야 겠죠??



 


위 처럼 기차가 한줄이 늘어나게 됩니다~




이렇게 삽입 연산을 표현할수 있겠네요~



알고리즘을 Pesudo Code로 보시겠습니다!



여기서 삽입은 중간 노드에 삽입이 되는 겁니다~




 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/*
    * L: 연결 리스트
    * pre: 앞 노드
    * x: 입력할 데이터 값
*/
 
insertMiddleNode(L, pre, x) {
    new <- getNode();
    new.data <- x;
    
    if (L == NULL) then {
        L <- new;
        new.link <- null;
    } else {
        new.link <- pre.link;
        pre.link <- new;
    }
}
cs








다음은 삭제 연산입니다!





2-2. 삭제 연산





잘 놀다가 헨리가 쉽게 질려버렸네요~



이제 그만하고 쉬겠다고 합니다!




헨리가 빠지면, 다시 서경석 뒤는 샘이겠네요~????




헨리가 가지고 있던 뒷 사람 이름을 앞사람(서경석)에게 넘겨주고 빠지게 됩니다!



 


다시 이렇게 바뀝니다!!!




알고리즘을 Pesudo Code로 보시겠습니다!




 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
/*
    * L: 연결 리스트
    * pre: 삭제 할 노드의 앞 노드
*/
 
deleteNode(L, pre) {
    if (L == NULL) then error;
    else {
        old <- pre.link;
        if (old == null) then return;
        pre.link <- old.link;
    }
    free old;
}
cs


삭제를 하고자하는 노드의 앞노드를 넘겨줘야 합니다!!!


삭제할 앞노드의 링크를 old로 담아서


old의 링크를 앞 노드의 링크로 넘겨주고


old는 메모리를 반환하게 되는 거죠~














자 그럼, 간단한 예제를 통해 확인해 보도록 합시다!!


자바로 작성된 String 값을 data로 두어서 예제를 만들어 보았습니다!



클래스 다이어 그램입니다!


 






ListNode.java


 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
package single;
 
public class ListNode {
    private String data;
    private ListNode link;
 
    // 생성자
    public ListNode() {
        this.data = null;
        this.link = null;
    }
 
    public ListNode(String data) {
        this.data = data;
        this.link = null;
    }
 
    public ListNode(String data, ListNode link) {
        this.data = data;
        this.link = link;
    }
 
    // Getter & Setter
    public String getData() {
        return data;
    }
 
    public void setData(String data) {
        this.data = data;
    }
 
    public ListNode getLink() {
        return link;
    }
 
    public void setLink(ListNode link) {
        this.link = link;
    }
}
 
cs







SingleLinkedList.java

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
 
package single;
 
public class SingleLinkedList {
    private ListNode head;
 
    // 생성자
    public SingleLinkedList() {
        head = null;
    }
 
    // 중간 노드 삽입
    public void insertMiddleNode(ListNode pre, String data) {
        ListNode newNode = new ListNode(data);
        newNode.setLink(pre.getLink()); // 삽입할 노드에 이전 노드의 참조 값 넘김
        pre.setLink(newNode); // 이전 노드의 참조 값을 삽입할 노드로 지정
    }
 
    // 마지막 노드에 삽입
    public void insertLastNode(String data) {
        ListNode newNode = new ListNode(data);
 
        // 리스트가 비어있으면 헤드로 지정
        if (head == null) {
            this.head = newNode;
        } else {
            ListNode tmp = head;
            while (tmp.getLink() != null)
                // 마지막 원소일때까지 탐색
                tmp = tmp.getLink();
            tmp.setLink(newNode);
        }
    }
 
    public void deleteNode(ListNode pre) {
        if (head == null) {
            System.out.println("리스트가 비어있습니다!");
            return;
        } else {
            ListNode old = pre.getLink(); // 삭제할 노드 가져와 old로 지정
            if (old == null)
                return;
            pre.setLink(old.getLink());
        }
    }
 
    public void deleteLastNode() {
        ListNode pre, tmp;
 
        if (head == null) {
            System.out.println("리스트가 비어있습니다!");
            return;
        }
 
        if (head.getLink() == null) {
            head = null;
        } else {
            pre = head;
            tmp = head.getLink();
 
            // 마지막 노드의 이전 노드의 링크가 널인 값인지 까지 탐색
            while (tmp.getLink() != null) {
                pre = tmp;
                tmp = tmp.getLink();
            }
 
            pre.setLink(null);
        }
    }
 
    public ListNode searchNode(String data) {
        ListNode tmp = this.head;
 
        while (tmp != null) {
            if (data == tmp.getData())
                return tmp;
            else
                tmp = tmp.getLink();
        }
 
        return tmp;
    }
 
    public void reverseList() {
        ListNode next = head;
        ListNode current = null;
        ListNode pre = null;
 
        while (next != null) {
            pre = current;
            current = next;
            next = next.getLink();
            current.setLink(pre);
        }
 
        head = current;
    }
 
    public void printList() {
        ListNode tmp = this.head;
        System.out.print("L = (");
 
        while (tmp != null) {
            System.out.print(tmp.getData());
            tmp = tmp.getLink();
 
            if (tmp != null) {
                System.out.print(", ");
            }
        }
 
        System.out.println(")");
    }
}
 
cs




SingleMain.java


 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
 
package single;
 
public class SingleMain {
    public static void main(String[] args) {
        SingleLinkedList L = new SingleLinkedList();
 
        System.out.println("(1) 공백 리스트에 노드 4개 삽입하기");
        L.insertLastNode("월");
        L.insertLastNode("화");
        L.insertLastNode("목");
        L.insertLastNode("금");
 
        L.printList();
 
        System.out.println("(2) 화 노드 뒤에 수 노드 삽입하기");
        ListNode pre = L.searchNode("화");
        if (pre == null) {
            System.out.println("검색 실패!! ");
        } else {
            L.insertMiddleNode(pre, "수");
            L.printList();
        }
 
        System.out.println("(3) 화 노드 삭제 하기");
        pre = L.searchNode("월");
        L.deleteNode(pre);
        L.printList();
 
        System.out.println("(4) 마지막 노드 삭제하기");
        L.deleteLastNode();
        L.printList();
    }
}
 
cs




결과는 아래와 같습니다!!



 




다른 카테고리의 글 목록

CSE/Data Structure 카테고리의 포스트를 톺아봅니다