🎇Linked List 구현하기

객체 생성

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;
}

---

반복

Iterator 객체 생성, next 메소드

기본적인 반복작업은 아래와 같다.

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());

LinkedList의 listIterator 메소드 만들기

//반복자를 생성해서 리턴해준다.
public ListIterator listIterator() {
	return new ListIterator();
}

ListIterator 객체

public class ListIterator{
	private Node lastReturned;
    private Node next;
    private int nextIndex;
    
    LisrIterator() {
    	next = head;
        nextIndex = 0;
    }
}

다음 노드의 값을 리턴하는 next 메소드

//이 메소드를 호출하면 cursor의 참조값이 기존 cursor.next로 변경된다.
public Object next() {
	lastReturned = next;
    next = next.next;
    nextIndex++;
    return lastReturned.data;
}

---

hasNext

public boolean hasNext() {
	return nextIndex < size();
 }

---

출처 opentutorials 생활코딩