Java의 간단한 단일 연결 목록 구현

게시 됨: 2013-11-27

Java에서 단일 연결 목록 구현

이 자습서에서는 Java에서 단일 연결 목록의 간단한 구현을 보여줍니다.

연결 목록은 다음과 같은 메모리에 있는 일련의 노드입니다.

  • 시작 노드가 있습니다.
  • 각 노드에는 다음 또는 자식 노드를 가리키는 포인터가 있습니다.
  • 노드에 자식 노드가 없으면 해당 포인터는 NULL로 설정됩니다.
  • 각 노드에는 데이터가 포함되어 있을 수 있습니다.
  • 연결 리스트에는 추가, 삭제, 노드의 데이터 변경, 노드 수 반환 등을 수행하여 리스트를 관리하는 기능도 있습니다.

아래 질문 중 하나가 있으면 올바른 블로그 게시물에 있습니다.

  • 연결 목록에서 주어진 노드를 삭제하는 방법
  • 단일 연결 리스트 중간에 있는 노드 삭제
  • 단일 연결 목록 :: 제거(삭제)
  • 단일 연결 목록에서 노드 제거

연결 리스트는 배열과 같은 용도로 사용됩니다. 그러나 연결 목록에는 몇 가지 장점이 있습니다. 배열은 고정된 크기이며(동적으로 할당되지 않는 한) 연결 목록은 필요에 따라 힙에서 새 메모리를 가져와 커질 수 있습니다. 목록을 배열에 저장한 다음 중간에 있는 항목을 삭제하면 간격을 메우기 위해 많은 항목을 아래로 이동해야 합니다. 그러나 연결 목록에서는 삭제할 노드 주위에 포인터를 다시 라우팅한 다음 삭제하기만 하면 됩니다.

다음은 단일 연결 목록의 간단한 구현입니다.

CrunchifyNode.java
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 com . crunchify . tutorials ;
 
/**
* @author Crunchify.com
*
*/
 
public class CrunchifyNode <V> {
     // instance variables
     private V element ;
     private CrunchifyNode <V> next ;
 
     // constructor first
     public CrunchifyNode ( ) {
         this ( null , null ) ;
     }
 
     public CrunchifyNode ( V element , CrunchifyNode <V> next ) {
         this . element = element ;
         this . next = next ;
     }
 
     public V getElement ( ) {
         return element ;
     }
 
     public CrunchifyNode <V> getNext ( ) {
         return next ;
     }
 
     public void setElement ( V element ) {
         this . element = element ;
     }
 
     public void setNext ( CrunchifyNode <V> next ) {
         this . next = next ;
     }
 
}

CrunchifySinglyLinkedList.java
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
139
140
141
142
143
144
145
package com . crunchify . tutorials ;
 
/**
* @author Crunchify.com
*
*/
 
public class CrunchifySinglyLinkedList <V> {
     // Instance Variables. Add the tail reference.
     protected CrunchifyNode <V> head , tail ;
     protected long size ;
 
     // Empty list constructor first
     public CrunchifySinglyLinkedList ( ) {
         head = null ;
         tail = null ;
         size = 0 ;
     }
 
     // Method to add CrunchifyNodes to the list. Storage space for the CrunchifyNode is already allocated in the calling method
     public void addFirst ( CrunchifyNode <V> CrunchifyNode ) {
         // Set the tail only if this is the very first CrunchifyNode
         if ( tail == null )
             tail = CrunchifyNode ;
         CrunchifyNode . setNext ( head ) ; // Make next of the new CrunchifyNode refer to the head
         head = CrunchifyNode ; // Give head a new value
 
         // change the size
         size ++ ;
     }
 
     // Add new CrunchifyNode after current CrunchifyNode, checking to see if we are at the tail
     public void addAfter ( CrunchifyNode <V> currentCrunchifyNode , CrunchifyNode <V> newCrunchifyNode ) {
         if ( currentCrunchifyNode == tail )
             tail = newCrunchifyNode ;
         newCrunchifyNode . setNext ( currentCrunchifyNode . getNext ( ) ) ;
         currentCrunchifyNode . setNext ( newCrunchifyNode ) ;
 
         // change the size
         size ++ ;
     }
 
     // Add new CrunchifyNode after the tail CrunchifyNode.
     public void addLast ( CrunchifyNode <V> CrunchifyNode ) {
         CrunchifyNode . setNext ( null ) ;
         tail . setNext ( CrunchifyNode ) ;
         tail = CrunchifyNode ;
         size ++ ;
     }
 
     // Methods to remove CrunchifyNodes from the list. (Unfortunately, with a single linked list. there is no way to remove last. Need a previous reference to do that.
     public CrunchifyNode <V> removeFirst ( ) {
         if ( head == null )
             System . err . println ( "Error:  Attempt to remove from an empty list" ) ;
 
         // save the one to return
         CrunchifyNode <V> temp = head ;
 
         // do reference manipulation
         head = head . getNext ( ) ;
         temp . setNext ( null ) ;
         size -- ;
 
         return temp ;
 
     }
 
     // Remove the CrunchifyNode at the end of the list. tail refers to this CrunchifyNode, but since the list is single linked, there is no way to refer to the CrunchifyNode before the tail CrunchifyNode. Need to traverse the list.
     public CrunchifyNode <V> removeLast ( ) {
         // Declare local variables/objects
         CrunchifyNode <V> CrunchifyNodeBefore ;
         CrunchifyNode <V> CrunchifyNodeToRemove ;
 
         // Make sure we have something to remove
         if ( size == 0 )
             System . err . println ( "Error:  Attempt to remove fron an empty list" ) ;
 
         // Traverse through the list, getting a reference to the CrunchifyNode before the trailer. Since there is no previous reference.
         CrunchifyNodeBefore = getFirst ( ) ;
 
         for ( int count = 0 ; count < size - 2 ; count ++ )
             CrunchifyNodeBefore = CrunchifyNodeBefore . getNext ( ) ;
 
         // Save the last CrunchifyNode
         CrunchifyNodeToRemove = tail ;
 
         // Let's do the pointer manipulation
         CrunchifyNodeBefore . setNext ( null ) ;
         tail = CrunchifyNodeBefore ;
         size -- ;
 
         return CrunchifyNodeToRemove ;
     }
 
     // Remove a known CrunchifyNode from the list. No need to search or return a value. This method makes use of a 'before' reference in order to allow list manipulation.
     public void remove ( CrunchifyNode <V> CrunchifyNodeToRemove ) {
         // Declare local variables/references
         CrunchifyNode <V> CrunchifyNodeBefore , currentCrunchifyNode ;
 
         // Make sure we have something to remove
         if ( size == 0 )
             System . err . println ( "Error:  Attempt to remove fron an empty list" ) ;
 
         // Starting at the beginning check for removal
         currentCrunchifyNode = getFirst ( ) ;
         if ( currentCrunchifyNode == CrunchifyNodeToRemove )
             removeFirst ( ) ;
         currentCrunchifyNode = getLast ( ) ;
         if ( currentCrunchifyNode == CrunchifyNodeToRemove )
             removeLast ( ) ;
 
         // We've already check two CrunchifyNodes, check the rest
         if ( size - 2 > 0 ) {
             CrunchifyNodeBefore = getFirst ( ) ;
             currentCrunchifyNode = getFirst ( ) . getNext ( ) ;
             for ( int count = 0 ; count < size - 2 ; count ++ ) {
                 if ( currentCrunchifyNode == CrunchifyNodeToRemove ) {
                     // remove current CrunchifyNode
                     CrunchifyNodeBefore . setNext ( currentCrunchifyNode . getNext ( ) ) ;
                     size -- ;
                     break ;
                 }
 
                 // Change references
                 CrunchifyNodeBefore = currentCrunchifyNode ;
                 currentCrunchifyNode = currentCrunchifyNode . getNext ( ) ;
             }
         }
 
     }
 
     // The gets to return the head and/or tail CrunchifyNodes and size of the list
     public CrunchifyNode <V> getFirst ( ) {
         return head ;
     }
 
     public CrunchifyNode <V> getLast ( ) {
         return tail ;
     }
 
     public long getSize ( ) {
         return size ;
     }
 
}

올바르게 처리되지 않은 버그나 기타 조건을 발견하면 언제든지 의견을 보내주십시오. 귀하의 피드백은 매우 감사합니다.