Data Structure and Algorithm/이론

LinkedList 코드

Razelo 2020. 12. 17. 16:51
package list.linkedlist.implementation;

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; //addFirst 한번 더 호출했을때.. 
		head = newNode;
		size++;
		if(head.next == null) {
			tail = head;
		}
	}
	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) {
		if(k == 0) {
			addFirst(input);
		}else {
			Node temp1 = node(k-1);   //이전 노드 
			Node temp2 =  temp1.next;
			Node newNode = new Node(input);
			temp1.next = newNode;
			newNode.next = temp2;
			size++;
			if(newNode.next == null) {
				tail = newNode;
			}
		}
	}
	
	public String toString() {
		if(head == null) {
			return "[]";
		}
		else {
			Node temp = head;
			String str = "[";
			while(temp.next != null) { 
				str += temp.data+", ";
				temp = temp.next;
			}
			str+=temp.data; //마지막 노드때문에 마지막은 temp.next가 null이니까. 
			return str+"]";
		}
	}
	public Object removeFirst() {
		Node temp = head;
		head = head.next;
		Object returnData = temp.data;
		temp = null;
		size--;
		return returnData;
	}
	public Object remove(int k) {
		if(k == 0) {
			return removeFirst();
		}
		Node temp = node(k-1);
		Node todoDeleted  = temp.next;
		temp.next = temp.next.next;
		Object returnData = todoDeleted.data;
		if(todoDeleted == tail) {
			tail = temp;
		}
		todoDeleted = null; //사실 이건 굳이 안해도 됨. 
		size--;
		return returnData;
	}
	public Object removeLast() {
		return remove(size-1);
	}
	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;
		int index = 0;
		while(temp.data != data) {
			temp = temp.next;
			index++;
			if(temp == null) { //가장 끝 노드 노달함 
				return -1;
			}
		}
		return index;
	}
	
	public ListIterator listIterator() {
		return new ListIterator();
	}
	public class ListIterator{
		private Node next;
		private Node lastReturned;
		private int nextIndex = 0;
		ListIterator(){
			next = head;
		}
		public Object next() {
			lastReturned = next;
			next = next.next;
			nextIndex++;
			return lastReturned.data;
		}
		public boolean hasNext() {
			return nextIndex<size();
		}
		public void add(Object input) {
			Node newNode = new Node(input);
			if(lastReturned == null) { // 첫번째 위치에 추가하는 작업 
				head = newNode;
				newNode.next = next;	
			}else {                    //중간에 끼워넣는 작업
				lastReturned.next = newNode;
				newNode.next = next;
			}
			lastReturned = newNode;
			nextIndex++;
			size++;
		}
		public void remove() {
			if(nextIndex == 0) {
				throw new IllegalStateException();
			}
			LinkedList.this.remove(nextIndex-1);
			nextIndex--;
		}
	}
	
}

 

package compare;

import list.arraylist.implementation.ArrayList;
import list.linkedlist.implementation.LinkedList;

public class Main {

	public static void main(String[] args) {
		ArrayList a = new ArrayList();
		a.addLast(10);
		a.addLast(20);
		a.addLast(30);
		a.addFirst(5);
		a.get(2);
		ArrayList.ListIterator ai = a.listIterator();
		while(ai.hasNext()) {
			if((int)ai.next() == 20) {
				ai.add(25);
			}
		}
		
		LinkedList l = new LinkedList();
		l.addLast(10);
		l.addLast(20);
		l.addLast(30);
		l.addFirst(5);
		l.get(2);
		LinkedList.ListIterator li = l.listIterator();
		while(li.hasNext()) {
			if((int)li.next() == 20) {
				li.add(25);
			}
		}
	}

}
반응형