[자료구조] List

단순 연결 리스트

 

public class LinkedList {
	public static void main(String[] args) {
		Node list = new Node(0, null);
		for(int i = 6; i >= 1; i--) {
			addtoFirst(i, list);			
		}
		printList(list);
        
		for(int i = 7; i <= 10; i++) {
			addtoLast(i, list);
		}
		printList(list);

		add(list, 3, -3);
		printList(list);

		delete(list, 3);
		printList(list);
	}
	static class Node {
		int value;
		Node next;
		Node(int value, Node next){
			this.value = value;
			this.next = next;
		}
	}
	public static void delete(Node list, int nth) {
		Node temp = list.next;
		
		Node prev = null;
		Node now = null;
		int cnt = 1;
		while(temp != null) {
			if(cnt == nth - 1) {
				prev = temp;
			}
			if(cnt == nth) {
				now = temp;
				break;
			}
			temp = temp.next;
			cnt++;
		}
		prev.next = now.next;
		
	}
	public static void add(Node list, int nth, int value) { // list의 3번째에 value을 
		Node temp = list.next;
		int cnt = 1;
		while(temp != null) {
			if(cnt++ == nth - 1) {
				Node back = temp.next;
				temp.next = new Node(value, back);
				break;
			}
			temp = temp.next;
		}
	}
	public static void addtoFirst(int value, Node list) {
		Node temp = list.next;
		list.next = new Node(value, temp);
	}
	public static void addtoLast(int value, Node list) {
		Node cursor = list;
		while(cursor.next!=null) {
			cursor = cursor.next;
		}
		cursor.next = new Node(value,null);
	}
	public static void printList(Node list) {
		Node cursor = list;
		while(cursor != null) {
			System.out.print(cursor.value+" ");
			cursor = cursor.next;
		}
		System.out.println();
	}
}

양방향 연결 리스트

 

public class DoublyLinkedList {
	static Node head = new Node(null, 0, null);
	static Node tail = new Node(head, 0 ,null);
	public static void main(String[] args) {

		head.next = tail;
		
		for(int value = 5; value >= 1; value--) {
			addtoFirst(value);	
			print(head);
		}
		for(int value = 6; value <= 10; value++) {
			addtoLast(value);	
			print(head);
		}
		delete(1);
		print(head);
		delete(9);
		print(head);
		delete(5);
		print(head);

	}
	
	public static void delete(int nth) {
		int cnt = 1;
		Node cur = head.next;
		while(cnt++ < nth) {
			cur = cur.next;
		}
		cur.prev.next = cur.next;
		cur.next.prev = cur.prev;
	}
	
	public static void addtoFirst(int value) {
		Node newNode = new Node(head, value, head.next);
		if(head.next == tail) {//head가 가리키고 있는 데이터가 없는 경우
			tail.prev = newNode;
		}
		head.next = newNode;
	}
	
	public static void addtoLast(int value) {
		Node prev = tail.prev;
		tail.prev = new Node(prev,value,tail);
		prev.next = tail.prev;
	}
	
	public static void print(Node list) {
		Node temp = list;
		while(temp != null) {
			System.out.print(temp.data+" ");
			temp = temp.next;
		}
		System.out.println();
	}
	public static void printReverse(Node list) {
		Node temp = list;
		while(temp != null) {
			System.out.print(temp.data+" ");
			temp = temp.next;
		}
		System.out.println();
	}
	static class Node {
		Node prev;
		int data;
		Node next;
		Node(Node prev, int data, Node next){
			this.prev = prev;
			this.data = data;
			this.next = next;
		}
	}
}