링크드리스트(2)

링크드리스트 데이터 중간 삽입 학습

 

//링크드 리스트에 데이터 추가
public class SingleLinkedList<T> {
	public Node<T> head = null;
	
	public class Node<T>{
		T data;
		Node<T> next = null;
		
		public Node(T data){
			this.data = data;
		}
	}
//	링크드리스트 노드 추가
	public void addNode(T data){
		if(head == null){
			head = new Node<T>(data);
		}else{
			Node<T> node =this.head;
			while(node.next != null){
				node = node.next;
			}
			node.next = new Node<T>(data);
		}
	}
//	링크드리스트 모두 출력
	public void printAll(){
		if(head != null){
			Node <T> node = this.head;
			System.out.println(node.data);
			while(node.next != null){
				node = node.next;
				System.out.println(node.data);
			}
		}
	}
//	특정값을 가진 노드 찾는 메서드
	public Node<T> search(T data){
		if(this.head == null){
			return null;
		}else{
			Node<T> node = this.head;
			while(node != null){
				if(node.data == data){
					return node;
				}else{
					node =node.next;
				}
			}
			return null;
		}
	}
	
//	링크드 리스트 데이터 사이에 데이터를 추가
	public void addNodeInside(T data, T isData){
		Node<T> searchedNode = this.search(isData);
		
		if(searchedNode == null){
			this.addNode(data);
		}else{
			Node<T> nextNode =searchedNode.next; //기존가리키던 노드를 따로 저장
			searchedNode.next = new Node<T> (data); //가리키던 노드가 새로운 노드를 가리키게 저장
			searchedNode.next.next = nextNode; //새로운노드가 기존가리키던 노드를 가리키게 저장
		}
	}
	
//	특정 노드를 삭제
	public boolean delNode(T isData){
		if(this.head == null){	//헤드가 null이면 데이터가 없다는 뜻 
			return false;
		}else{ //데이터가 있다면 헤드를 검사
			Node<T> node = this.head; 
			if(node.data == isData){	//헤드데이터가 삭제할 데이터가 맞으면 
				this.head = this.head.next; // 다음데이터를 헤드로 지정
				return true;
			}else{ //헤드데이터가 아니라면 
				while(node.next != null){  //모든 데이터 검사 (순회)
					if(node.next.data == isData){ 
						node.next = node.next.next; 
						return true;
					}
					node = node.next;
				}
				return false;
			}
		}
	}
	
	public static void main(String[] args) {
		
		SingleLinkedList<Integer> MyLinkedList = new SingleLinkedList<Integer>();
//		링크드리스트 생성하고, 1, 2, 3 데이터 넣기
		MyLinkedList.addNode(1);
		System.out.println(MyLinkedList.head.data); //1
		MyLinkedList.addNode(2);
		System.out.println(MyLinkedList.head.next.data); //2
		MyLinkedList.addNode(3);
		System.out.println("##################################");
		MyLinkedList.printAll();
		System.out.println("##################################");
//		1 데이터 뒤에 5 넣어보기
		MyLinkedList.addNodeInside(5, 1);
		MyLinkedList.printAll();
		System.out.println("##################################");
//		3 데이터 뒤에 6 넣어보기
		MyLinkedList.addNodeInside(6, 3);
		MyLinkedList.printAll();
		System.out.println("##################################");

//		없는 데이터를 찾도록 해서, 맨 마지막에 데이터 넣기
		MyLinkedList.addNodeInside(7, 20);
		MyLinkedList.printAll();  // 1 5 2 3 6 7
		System.out.println("##################################");

//		테스트: 중간 노드 삭제
		MyLinkedList.delNode(3);
		MyLinkedList.printAll(); // 1 5 2 6 7
		System.out.println("##################################");
		
//		테스트: 맨 앞의 노드(헤드 ) 삭제
		MyLinkedList.delNode(1);
		MyLinkedList.printAll();// 5 2 6 7
		System.out.println("##################################");
		
//		테스트: 맨 마지막 노드 삭제
		MyLinkedList.delNode(7);
		MyLinkedList.printAll(); // 5 2 6
		System.out.println("##################################");

//		테스트: 없는 노드 삭제 시도
		System.out.println(MyLinkedList.delNode(20));
		
		
	}

}

 

 

public class DoubleLinkedList<T> {
//	더블 링크드리스트(Doubly linked list)기본 구조
//	이중 연결이라고도 한다.
//	장점 : 양방향으로 연결되어 있어서 노드 탐색이 양쪽으로 모두 가능
	
	public Node<T> head = null;
	public Node<T> tail = null;
	
	public class Node<T>{
		T data;
		Node<T> prev =null;
		Node<T> next =null;
		
		public Node(T data){
			this.data = data;
		}
	}
	
//	데이터값 삽입
	public void addNode(T data){
		if(this.head == null){
			this.head = new Node<T>(data);
			this.tail = this.head;
		}else{
			Node<T> node = this.head;
			while(node.next != null){
				node = node.next;
			}
			node.next = new Node<T>(data);
			node.next.prev = node;
			this.tail =node.next;
		}
	}
	
	public void printAll(){
		if(this.head != null){
			Node<T> node = this.head;
			System.out.println(node.data);
			while(node.next != null){
				node = node.next;
				System.out.println(node.data);
			}
		}
	}
//	 head 부터 특정 노드를 찾는 메서드 추가하기
	public T searchFromHead(T isData){
		if(this.head == null){
			return null;
		}else{
			Node<T> node = this.head;
			while(node != null){
				if(node.data == isData){
					return node.data;
				}else{
					node = node.next;
				}
			}
			return null;
		}
	}
	
//	 tail 부터 특정 노드를 찾는 메서드 추가하기
	public T searchFromTail(T isData){
		if(this.head == null){
			return null;
		}else{
			Node<T> node = this.tail;
			while(node != null){
				if(node.data == isData){
					return node.data;
				}else{
					node = node.prev;
				}
			}
			return null;
		}
	}
	
	public static void main(String[] args) {
		DoubleLinkedList<Integer> MyLinkedList = new DoubleLinkedList<Integer>();
		
//		테스트 : 데이터 삽입
		MyLinkedList.addNode(1);
		MyLinkedList.addNode(2);
		MyLinkedList.addNode(3);
		MyLinkedList.addNode(4);
		MyLinkedList.addNode(5);
		MyLinkedList.printAll();
		System.out.println("##################################");

		
//		테스트 : head 부터 특정 노드를 찾는 메서드 추가하기
		System.out.println(MyLinkedList.searchFromHead(1));
//		테스트 : tail 부터 특정 노드를 찾는 메서드 추가하기
		System.out.println(MyLinkedList.searchFromTail(1));
		System.out.println("##################################");
		
	}

}

 

더블링크드리스트 학습(계속)