자료구조

LinkedList - 2

1편에 이어서 linkedList를 공부한다

이번엔 삭제와 iterator를 구현해보려고 한다.
iterator는 linked list 내부적으로 훓는것이다.
외부에서 for문을 사용하여 데이터를 꺼낼 수 있지만
순차적 접근을 처음부터 해야하기 때문에 비효율적이다
내부에서 index를 유지한채로 반복을 돌면 처음부터 다시 돌 필요가 없다.

구현

[Doubly linked list] []
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
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
public class LinkedList<E> {
	private int size;
	private Node<E> head;
	private Node<E> tail;
	
	public static class Node<E> {
		E item;
		transient Node<E> next;
		Node<E> prev;
		
		public Node(Node<E> prev, E element, Node<E> next) {
			this.item = element;
			this.next = next;
			this.prev = prev;
		}
		
	}
	
	public int getSize() {
		return size;
	}
	
	public void addFirst (E element) {
		final Node<E> prevHead = head;
		
		Node<E> newNode = new Node<E>(null, element, head);
		head = newNode;
		
		if(prevHead == null) tail = head;
		else prevHead.prev = newNode;
		
		size++;
	}
	
	public void addLast (E element) {
		final Node<E> prevTail = tail;
		
		Node<E> newNode = new Node<E>(tail, element, null);
		tail = newNode;
		
		if(prevTail == null) head = tail;
		else prevTail.next = newNode;
		
		size++;
	}
	
	public Node<E> node(int index) {
		if(index < (size >> 1)){
		    Node<E> x = this.head; 
		    for(int i = 0; i < index; i++) {
			    x = x.next;
		    }
			return x;            
		} else {
		    Node<E> x = this.tail; 
		    for(int i = size - 1; i > index; i--) {
			    x = x.prev;
		    }
			return x;
		}
	}
	
	public void add(int index, E element) {
		Node<E> prev = node(index);
		Node<E> next = node(index+1);
		Node<E> newNode = new Node<E>(prev, element, next);
		prev.next = newNode; 
		next.prev = newNode;
		size++;
	}
	
	public String toString() {
		if(head == null){
		        return "[]";
		    }       
		 
		 StringBuffer sb = new StringBuffer("[" + String.valueOf(this.head.item));
		    
		 for (Node<E> x = this.head.next; x != null; x = x.next) {
			 sb.append("," + String.valueOf(x.item));
         }
		 
		 return sb.append("]").toString();
	}
	//여기서부터 추가코드
	//첫번째 요소 삭제
	//head의 다음 요소를 head로 지정하고 prev를 null로 바꾼다.
	//사이즈를 줄여준다.
	public void removeFirst(){
		Node<E> newHead = this.head.next;
		newHead.prev = null;
		this.head = newHead;
		size--;
	}
	
	//위와 반대로 실행한다.
	public void removeLast(){
		Node<E> newTail = this.tail.prev;
		newTail.next = null;
		this.tail = newTail;
		size--;
	}
	
	//원하는 요소의 이전 요소와 다음 요소를 불러온다
	//이전요소의 다음요소 그리고 다음요소의 이전요소를 바꿔준다.
	//사이즈를 줄여준다
	public E remove(int index) {
		Node<E> prev = node(index-1);
		Node<E> next = node(index+1);
		Node<E> returnNode = prev.next;
		prev.next = next;
		next.prev = prev;
		size--;
		return returnNode.item;
	}
	
	//데이터를 받아서 반복을 돌며 데이터가 일치하면 위치값을 반환한다.
	public int indexOf(E element) {
		int index = 0;
		for(Node<E> x = head; x != null; x = x.next) {
			if(x.item.equals(element)) return index;
			index++;
		}
		return -1;
	}
	
	//ListIterator를 생성해준다.
	public ListIterator<E> listIterator() {
		return new ListIterator<E>(); 
	}
	
	class ListIterator<E>{
		//다음 요소와 마지막 반환 요소 다음 요소의 위치값을 가지고 있다.
		private Node<E> lastReturned;
		private Node<E> next;
		private int nextIndex;
		
		//생성할때 head를 다음요소로 넣는다.
		private ListIterator() {
			//이부분에서 (Node<E>)로 
			//명시적 형변환이 왜 필요한지 모르겠다.
			//혹시 아시는분은 댓글로 알려주세요...
			next = (Node<E>) head;
		}

        //다음요소가 있는지 확인한다.
		//다음요소의 위치값이 사이즈보다 작은지 여부를 반환한다.
		public boolean hasNext() {
			return nextIndex < size;
		}
        
		//이전 반환 요소를 다음 요소로 바꿔주고
		//다음 요소를 다음 다음 요소로
		//위치값을 증가시키고
		//바꿔준 반환 요소의 데이터를 반환한다.
		public E next() {
			lastReturned = next;
			next = next.next;
			nextIndex++;
			return lastReturned.item;
		}
		
		//이전요소가 있는지 확인한다.
		public boolean hasPrevious() {
			return nextIndex > 0;
		}
		
		//만약 다음요소가 null이면 마지막 반환요소를 tail로 바꿔준다.
		//나머진 next와 동일하다
		public E previous() {
			lastReturned = next = (next == null ? (Node<E>) tail : next.prev);
			nextIndex--;
			return lastReturned.item;
		}
		
		//다음 위치값을 반환한다.
        public int nextIndex() {
            return nextIndex;
        }
        
		//이전 위치값을 반환한다.
        public int previousIndex() {
            return nextIndex - 1;
        }
	}
}

출력테스트

[Doubly linked list] []
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
public static void main(String[]args) {
	LinkedList<String> list = new LinkedList<String>();
	list.addFirst("a");
	list.addFirst("b");
	list.addFirst("c");
	list.addFirst("d");
	list.addFirst("e");
	list.addFirst("f");
	list.addFirst("g");
	list.addFirst("h");
	list.addFirst("i");

	System.out.println(list.toString());
	
	//처음 삭제
	list.removeFirst();
	
	//마지막 삭제
	list.removeLast();

	//중간삭제
	System.out.println("remove : " + list.remove(1));

	
	//인덱스 구하기
	System.out.println("e.index : " + list.indexOf("e"));

	LinkedList<String>.ListIterator<String> it = list.listIterator();

	System.out.println("next-------------");
	while (it.hasNext()) {
		System.out.print(it.next());
	}
	
	System.out.println("," + it.nextIndex());
	
	System.out.println("prev-------------");
	while (it.hasPrevious()) {
		System.out.print(it.previous());
	}
	System.out.println("," + it.previousIndex());

}

출력결과

[Doubly linked list] []
1
2
3
4
5
6
7
[i,h,g,f,e,d,c,b,a]
remove : g
e.index : 2
next-------------
hfedcb,6
prev-------------
bcdefh,-1

결과

간단하게 LinkedList를 구현해봤다.
어떤 구조인지 대충 알고 있었는데 실제로 코드를 보니
더 확실히 이해가 된 것 같다.
구현해보면서 아직 모자란 부분을 많이 알 수 있었다.
제너릭이나 인터페이스 상속을 더 공부해봐야겠다.

혹시 잘못된 부분이나 미흡한 부분은 댓글로 남겨주시면
바로 수정하겠습니다.

끝!

공유하기