본문 바로가기
전산 기초/자료구조

[자료구조/java] 단순 연결 리스트 (Linked List)

은져미 2015. 10. 25. 18:32


* 단순 연결 리스트 (Linked List)



- 노드가 하나의 링크 필드에 의해서 다음 노드와 연결되는 구조를 가진 연결 리스트 



* 장점 :  삽입, 삭제가 빠르다.

하지만 중간에 있는 노드를 삭제하는 경우 탐색에 소요되는 시간이 있기 때문에

맨 앞에 있는 요소를 삽입, 삭제하는 경우 O(1), 

중간요소를 삽입, 삭제하는 경우 O(n)의 시간복잡도를 가진다.

* 단점 : 탐색이 느리다.

탐색의 경우 배열이 index를 이용하기 때문에 더빠르다.



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
Test.java
 
package LinkedList;
 
public class Test {
   public static void main(String[] args) {
      LinkedList list = new LinkedList();
      System.out.println("(1) 공백 리스트에 노드 3개 삽입하기");
      list.insertLastNode("월");
      list.insertLastNode("수");
      list.insertLastNode("일");
      list.printList();
      
      System.out.println("(2) \"수\"노드 뒤에 \"금\" 노드 삽입하기");
      ListNode pre = list.searchNode("수");
      
      if(pre==null){
         System.out.println("검색 실패 >> 찾는 데이터가 없습니다.");
      }else{
         list.insertMiddleNode(pre, "금");
      }
      list.printList();
      
      System.out.println("(3) 리스트의 첫번째에 노드 추가하기");
      list.insertFirstNode("토");
      list.printList();
      
      System.out.println("(4) 리스트의 마지막 노드 삭제하기");
      list.deleteLastNode();
      list.printList();
      
      System.out.println("(5) 리스트의 중간 노드 \"수\" 삭제하기");
      list.deleteMiddleNode("수");
      list.printList();
      
      System.out.println("(6) 리스트의 첫번째 노드 삭제하기");
      list.deleteFirstNode();
      list.printList();
      
      System.out.println("(7) 리스트 역순으로 출력하기");
      list.reverseList();
      list.printList();
   }
}



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
ListNode.java
 
package LinkedList;
 
public class ListNode {
   String data;
   ListNode next;
   
   public ListNode(){
      this.data = null;
      this.next = null;
   }
   
   public ListNode(String data){
      this.data = data;
      this.next = null;
   }
   
   public ListNode(String data, ListNode next){
      this.data = data;
      this.next = next;
      this.next = null;
   }
   
   public String getData(){
      return this.data;
   }
}



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
LinkedList.java
 
package LinkedList;
 
public class LinkedList {
   private ListNode head;
   
   public LinkedList() {
      this.head = null;
   }
   
   void insertLastNode(String str){
      ListNode node = new ListNode(str);
      if(head == null){
         head = node;
      }else{
         ListNode current = head;
         while(current.next!=null){
            current = current.next;
         }
         current.next = node;
      }
   }
 
   void insertMiddleNode(ListNode pre, String str){
      ListNode node = new ListNode(str);
      if(head == null){
         head = node;
      }else{
         ListNode current = head;
         while(current.next!=pre){
            current = current.next;
         }
         current = current.next;
         node.next = current.next;
         current.next = node;
      }
   }
 
   void insertFirstNode(String str){
      ListNode node = new ListNode(str);
      if(head == null){
         head = node;
      }else{
         ListNode current = head;
         node.next = current;
         head = node;
      }
   }
 
   void deleteLastNode(){
      if(head==null){
         System.out.println("지울 노드가 존재하지 않습니다.");
      }else{
         ListNode prev = head;
         ListNode current = head.next;
         while(current.next!=null){
            prev = current;
            current = current.next;
         }
         prev.next = null;
      }
   }
 
   void deleteMiddleNode(String str){
      ListNode node = new ListNode(str);
      if(head==null){
         System.out.println("지울 노드가 존재하지 않습니다.");
      }else{
         ListNode prev = head;
         ListNode current = head.next;
         while(current.data!=node.data){
            prev = current;
            current = current.next;
         }
         prev.next = current.next;
      }
   }
 
   void deleteFirstNode(){
      if(head==null){
         System.out.println("지울 노드가 존재하지 않습니다.");
      }else{
         head = head.next;
      }
   }
 
   ListNode searchNode(String str){
      ListNode node = new ListNode(str);
      if(head==null){
         System.out.println("노드가 비어있습니다.");
         return null;
      }else{
         ListNode current = head;
         while(current.data!=node.data){
            current = current.next;
         }
         return current;
      }
   }
 
   void reverseList(){
      ListNode next = head;
      ListNode current = null;
      ListNode prev = null;
 
      while(next!=null){
          prev = current;
          current = next;
          next = next.next;
          current.next = prev;
      }
      head = current;
   }
 
   void printList(){
      if(head==null){
         System.out.println("출력할 리스트가 존재하지 않습니다.");
      }else{
         ListNode current = head;
         System.out.print("[");
         while(current.next!=null){
            System.out.print(current.data + " ");
            current = current.next;
         }
         System.out.print(current.data);
         System.out.print("]");
         System.out.println();
      }
   }
}



저작자표시 비영리 동일조건

'전산 기초 > 자료구조' 카테고리의 다른 글

[자료구조/java] 스택 (Stack) - 1차원 배열, 연결리스트 구현  (0) 2015.10.31
[자료구조/java] 다항식의 연결 자료구조 표현  (0) 2015.10.30
[자료구조/java] 이중 연결 리스트 (Doubly Linked List)  (0) 2015.10.27
[자료구조/java] 원형 연결 리스트 (Circular Linked List)  (0) 2015.10.26
[자료구조] 자료구조 시작  (0) 2015.10.24

'전산 기초/자료구조' Related Articles

티스토리툴바