LinkedList.java
public class LinkedList
Main.java
public class Main {
public static void main(String[] args) {
LinkedList numbers = new LinkedList();
}
}
노드는 실제로 데이터가 저장되는 그릇과 같은 것이다. 자바는 객체지향 언어이기 때문에 노드는 객체로 만들기 딱 좋은 대상이며, 노드 객체는 리스트의 내부 부품이기 때문에 외부에는 노출되지 않는 것이 좋다. 그래서 private
로 지정한다.
- head : 첫 번째 노드를 지정하는 참조값
- tail : 마지막 노드
- size : 노드의 크기, 노드 변경시 수정 필요
- data : 노드의 값 (객체 Node의 내부 변수)
- next : 다음 노드의 참조값 (객체 Node의 내부 변수)
public class LinkedList {
// 첫번째 노드를 가리키는 필드
private Node head;
private Node tail;
private int size = 0;
private class Node{
private Object data; //데이터가 저장될 필드
private Node next; //다음 노드를 가리키는 필드
public Node(Object input) {
this.data = input;
this.next = null;
}
public String toString() { //노드의 내용 출력
return String.valueOf(this.data)
}
}
}
public void addFirst(Object input){
Node newNode = new Node(input); //노드 생성
newNode.next = head; //새로운 노드의 다음 노드로 헤드를 지정
head = newNode; //head를 새로운 노드로 지정
size++;
if(head.next == null)
tail = head;
}
리스트의 끝에 데이터를 추가할 때는 tail
을 사용한다. tail
없이도 구현이 가능하지만, tail
이 없으면 마지막 노드를 찾아야 한다. 마지막 노드를 찾는 것은 첫 노드부터 마지막 노드까지 순차적으로 탐색을 해야 하기 때문에 최악의 상황이라고 할 수 있다. 그래서 tail
을 사용한다.
public void addLast(Object input) {
Node newNode = new Node(input); //노드 생성
if(size == 0) //리스트의 노드가 없는 경우, 첫번째 노드로 추가하는 메소드 사용
addFirst(input);
else {
tail.next = newNode; //마지막 노드의 다음 노드로 생성한 노드를 지정
tail = newNode; //마지막 노드를 갱신
size++;
}
}
Node node(int index) {
Node x = head;
for(int i = 0; i < index; i++)
x = x.next;
return x;
}
public void add(int k, Object input){
// k = 0이면 첫 번째 노드에 추가하는 것, addFirst 사용
if(k==0)
addFirst(input);
else {
Node temp1 = node(k-1); //k-1번째 노드를 temp1로 지정
Node temp2 = temp1.next; //k번째 노드를 temp2로 지정
Node newNode = new Node(input);
temp1.next = newNode; //temp1의 다음 노드로 새로운 노드를 지정
newNode.next = temp2; //새로운 노드 다음 노드로 temp2 지정
size++;
if(newNode.next == null)
tail = newNode;
//새로운 노드의 다음 노드가 없다면
//새로운 노드가 마지막 노드이기 때문에
}
}
public String toString() {
if(head == null)
return "-1"; //노드가 없다면 -1을 출력
//탐색 시작
Node temp = head;
String str = " ";
//다음 노드가 없을 때 까지 반복문을 실행한다.
//tail은 다음 노드가 없기 때문에, 마지막 노드는 제외된다.
while(temp.next != null) {
str += temp.data +", ";
temp = temp.next;
}
//마지막 노드 출력결과에 포함
str += temp.data;
return str;
public Object removeFirst() {
Node temp = head; //첫번째 노드를 head로 지정
head = temp.next; //head의 값을 두번째 노드로 변경
Object returnData = temp.data; //데이터 삭제 전 리턴할 값을 임시 변수에 담아둔다.
temp = null;
size--;
return returnData;
}
public Object remove(int k) {
if(k == 0)
return removeFirst();
Node temp = node(k-1); //k-1번째 node를 temp의 값으로 지정
Node todoDeleted = temp.next;
//삭제할 노드를 todoDeleted에 기록
// 삭제 노드를 지금 제거하면 삭제 앞 노드와 삭제 뒤 노드를 연결할 수 없다.
temp.next = temp.next.next;
//삭제 앞 노드의 다음 노드로 삭제 뒤 노드를 지정한다.
Object returnData = todoDeleted.data;
//삭제된 데이터를 리턴하기 위해서 returnData에 저장한다.
if(todoDeleted == tail)
tail = temp;
todoDeleted = null;
size--;
return returnData;
}
public int size() {
return size;
}
public Object get(int k){
Node temp = node(k);
return temp.data;
}
public int indexOf(Object data){
Node temp = head; //탐색 대상이 되는 노드를 temp로 지정한다.
int index = 0; //탐색 대상의 엘리먼트
while(temp.data != data) { //탐색 값과 탐색 대상의 값을 비교
temp = temp.next;
index++;
if(temp == null) //더 이상 탐색할 대상이 없다는 것
return -1;
}
return index;
}
기본적인 반복작업은 아래와 같다.
for(int i = 0; i<numbers.size(); i++)
System.out.println(numbers.get(i));
위처럼 해도 되지만, Linked List
에서는 바람직 하지 않다. ArrayList
와 다르게 LinkedList
에서의 get은 효율적이지 않기 때문이다. get은 호출할 때마다 내부적으로 반복문이 실행된다. 이런 경우에는 Iterator
를 사용하는 것이 유리하다.
Iterator
는 내부적으로 반복 처리된 노드가 무엇인지에 대한 정보를 유지하기 때문이다.
ListIterator it = numbers.listIterator();
while(it.hasNext())
System.out.println(it.next());
//반복자를 생성해서 리턴해준다.
public ListIterator listIterator() {
return new ListIterator();
}
public class ListIterator{
private Node lastReturned;
private Node next;
private int nextIndex;
LisrIterator() {
next = head;
nextIndex = 0;
}
}
//이 메소드를 호출하면 cursor의 참조값이 기존 cursor.next로 변경된다.
public Object next() {
lastReturned = next;
next = next.next;
nextIndex++;
return lastReturned.data;
}
public boolean hasNext() {
return nextIndex < size();
}