[자료구조] 02. Single Linked List 구현하기

링크드 리스트(동적 연결 리스트)

1) 논리적으로 연속된 리스트

2) 필요할 때 공간을 할당할 수 있다.

3) 검색: 임의의 검색은 순차적으로검색하다가 나타나면 땡큐! ArrayList와 동일, 정렬시는 이진검색/보간검색을 통해 바로index로 점프! (데이터가 고르게 분포되어 있어야 유리한 구조) 이중 연결 리스트일 경우, Head 또는 Tail로부터 접근을 결정할 수 있고 바로 jump는 안 된다.

4) 추가: 새로운 객체 할당 → 이전 element에 새로운 객체를 가리키게 함

5) 삽입: 새로운 객체 할당 → 이전 element가 나를 지칭하게 만듦 → 나는 다음 element를 가리키게 함

6) 삭제: 대상의 이전 element가 다음 element를 가리키게 함.

7) 확장: 추가와 동일함

public class LinkedListMain{
	public static void main(String args[]){
		LinkedList<String> L = new LinkedList<String>();
		System.out.println("(1) 공백 리스트에 노드 3개 삽입하기");
		L.insertLastNode("월");
		L.insertLastNode("수");
		L.insertLastNode("일");
		L.printList();

		System.out.println("(2) 수 노드 뒤에 금 노드 삽입하기");
		ListNode<String> pre = L.searchNode("수");
		if(pre == null) 
			System.out.println("검색실패>> 찾는 데이터가 없습니다.");
		else{
			L.insertMiddleNode(pre, "금");
			L.printList();
		}

		System.out.println("(3) 리스트의 노드를 역순으로 바꾸기");
		L.reverseList();
		L.printList();

		System.out.println("(4) 리스트의 마지막 노드 삭제하기");      
		L.deleteLastNode();
		L.printList();
	}
}

class LinkedList<E>{
	private ListNode<E> head;
	public LinkedList(){
		head = null;
	}
	public void insertMiddleNode(ListNode<E> pre, E data){       
		ListNode<E> newNode = new ListNode<E>(data);
		newNode.link = pre.link;
		pre.link = newNode;
	}

	public void insertLastNode(E data){
		ListNode<E> newNode = new ListNode<E>(data);
		if(head == null){
			this.head = newNode;
		}
		else{
			ListNode<E> temp = head;
			while(temp.link != null) 
				temp = temp.link;
			temp.link = newNode;
		}
	}

	public void deleteLastNode(){
		ListNode<E> pre, temp;
		if(head == null)  return;
		if(head.link == null){
			head = null;
		}
		else{
			pre = head;
			temp = head.link;
			while(temp.link != null){
				pre = temp;
				temp = temp.link;
			}
			pre.link = null;
		}
	}

	public ListNode<E> searchNode(E data){
		ListNode<E> temp = this.head;
		while(temp != null){
			if(data.equals(temp.getData()))  
				return temp;
			else 
				temp = temp.link;
		}
		return  temp;
	}

	public void reverseList(){
		ListNode<E> next = head;
		ListNode<E> current = null;
		ListNode<E> pre = null;
		while(next != null){
			pre = current;
			current = next;
			next = next.link;
			current.link = pre;
		}
		head = current;
	}

	public void printList(){
		ListNode<E> temp = this.head;
		System.out.print("L = (");
		while(temp != null){
			System.out.print(temp.getData());
			temp = temp.link;
			if(temp != null){
				System.out.print(", ");
			}			
		}
		System.out.println(")");
	}
}

// 저장공간
class ListNode<E>{
	private E data;			// 저장소
	public ListNode link;	// 다음 노드를 가리킨다.
	public ListNode(){
		this.data = null;
		this.link = null;
	}
	public ListNode(E data){
		this.data = data;
		this.link = null;
	}
	public ListNode(E data, ListNode link){
		this.data = data;
		this.link = link;
	}
	public E getData(){
		return  this.data;
	}
}