Chapter2 Linked Lists

Createing a Linked List

LinkedList는 각 노드마다 다음 노드의 주소값을 가지고 있는 List입니다. 배열처럼 인덱스를 가지고 탐색하는것이 아니고 연결된 리스트를 하나하나 탐색하며 찾다보니 탐색에 대한 시간복잡도는 O(n)입니다. 대신 삽입/삭제 연산시에는 배열은 Shift하는 과정이 필요해서 복잡도가 O(n)이지만 LinkedList는 해당 노드의 앞뒤의 연결부분만 바꿔주면 되기 때문에 상수시간의 복잡도로 처리가 가능하다는 장점을 가지고 있습니다.

중간에서 삭제를 하거나 삽입을 하는 경우엔 케이스를 나눠서 구현하면 쉽게 구현할 수 있다.

1. 헤드가 타겟 노드인 경우
2. 타겟노드가 중간에 있는 경우
3. 리스트의 마지막 노드가 타겟 노드인 경우

때문에 위의 코드처럼 3가지 경우를 나눠서 연결 상태를 적절히 수정하 구현할 수 있다.

Interview Questions

2.1 연결리스트에서 중복 원소를 제거하는 알고리즘을 작성하라. (버퍼 배열을 사용하지 않고 구현)

2.2 연결리스트에서 마지막 요소를 반환하는 알고리즘을 작성하라.

2.3 연결리스트에서 가운데 요소를 삭제하는 알고리즘을 작성하라.

2.4 두 연결리스트가 주어질때 (각 노드는 한자리 수), 두 연결리스트에서 각각의 노드를 더한 새로운 노드를 구하는 알고리즘을 작성하라.

input : (3->1->5)+(5->9->2)

output : 8->0->7

전체 소스 코드

package chapter2;

import java.util.HashMap;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		LinkedList linkedList = new LinkedList();
		linkedList.appendToTail(1);
		linkedList.appendToTail(2);
		linkedList.appendToTail(3);
		linkedList.printNode();
		
		
		
		LinkedList linkedList2 = new LinkedList();
		linkedList2.appendToTail(5);
		linkedList2.appendToTail(6);
		linkedList2.appendToTail(7);
		linkedList2.appendToTail(100);
		linkedList2.printNode();

		LinkedList sumLinkedList = linkedList.sumLinkedList(linkedList, linkedList2);
		sumLinkedList.printNode();
		
	}


}

class Node{
	Node next;
	int data;
	
	public Node(int data) {
		this.data = data;
	}
	
}

class LinkedList{
	
	Node head;
	
	public void appendToTail(int data) {
		if(head==null) {
			appendHead(data);
		}
		else {
			Node currentNode = this.head;
			Node newNode = new Node(data);
			while(currentNode.next != null) {
				currentNode = currentNode.next;
			}
			currentNode.next = newNode;	
		}
	}
	
	public void appendHead(int data) {
		Node newNode = new Node(data);
		this.head = newNode;
	}
	
	
	public void deleteNode(int data) {
		Node currentNode = this.head;
		// head node
		if(currentNode.data == data) {
			this.head = currentNode.next;
			return;
		}
		
		Node prevNode = this.head;
		while(currentNode.next != null) {
			prevNode = currentNode;
			currentNode = currentNode.next;
			// middle node
			if(currentNode.data == data) {
				prevNode.next = currentNode.next;
				currentNode = null;
				return;
			}
			// last node
			if(currentNode.next == null && currentNode.data==data) {
				prevNode.next = null;
				return;
			}
		}
	}
	
	public void printNode() {
		Node head = this.head;
		boolean isEndOfList = false;
		while(!isEndOfList) {
			System.out.print(head.data + " ");
			if(head.next == null) {
				isEndOfList = true;
			}
			else {
				head = head.next;
			}
		}
		System.out.println();
	}
	
	public void deleteDuplicate() {
		Node currentNode = this.head;
		boolean isEndOfNode = false;
		HashMap hashMap = new HashMap<>();
		while(!isEndOfNode) {
			if(hashMap.get(currentNode.data) != null) {
				deleteNode(currentNode.data);
			}
			else {
				hashMap.put(currentNode.data, true);
			}
			
			if(currentNode.next == null) {
				isEndOfNode = true;
			}
			else {
				currentNode = currentNode.next;
			}
		}
	}
	
	public Node getLast() {
		Node currentNode = this.head;
		while(currentNode.next != null) {
			currentNode = currentNode.next;
		}
		return currentNode;
	}
	
	public LinkedList sumLinkedList(LinkedList l1, LinkedList l2) {
		LinkedList resultLinkedList = new LinkedList();
		boolean isEndOfTask = false;
		if(l1.head == null) {
			return l2;
		}
		else if(l2.head == null) {
			return l1;
		}
		
		Node l1Node = l1.head;
		Node l2Node = l2.head;
		
		while(!isEndOfTask) {
			int l1Value = l1Node.data, l2Value = l2Node.data;
			resultLinkedList.appendToTail(l1Value+l2Value);
			if(l1Node.next == null && l2Node.next == null) {
				isEndOfTask = true;
			}
			else if(l1Node.next == null) {
				while(l2Node.next != null) {
					l2Node = l2Node.next;
					resultLinkedList.appendToTail(l2Node.data);
				}
				isEndOfTask = true;
			}
			else if(l2Node.next == null) {
				while(l1Node.next != null) {
					l1Node = l1Node.next;
					resultLinkedList.appendToTail(l1Node.data);
				}
				isEndOfTask = true;
			}
			else {
				l1Node = l1Node.next;
				l2Node = l2Node.next;
			}
		}
		
		return resultLinkedList;
	}
}

#원문

[Cracking the coding interview PDF]