[자료구조]배열(Array)과 연결 리스트(Linked List)

1. 배열(Array)

• 배열은 같은 타입의 원소들을 효율적으로 관리할 수 있는 자료 구조
• 배열은 하나의 변수 이름으로 동일한 타입의 데이터를 그룹화하여 관리 가능
• 배열의 요소를 일렬로 나열하고 각 요소에 인덱스를 사용하여 원하는 데이터에 접근 가능

 

2. 연결 리스트(Linked List)

• 배열의 약점인 삽입과 삭제 작업에 강한 자료 구조로 연결 리스트가 있음
• 연결 리스트는 각 요소를 포인터라고 부르는 화살표에 의해 한 줄로 나열한 것

• 연결 리스트의 종류
  • 단방향 연결 리스트는 각 노드를 연결하는 포인터가 어느 한쪽 방향이 되도록 한 것
  • 양방향 연결 리스트는 각 노드를 연결하는 포인터가 양방향이 되도록 한 것

 

3. 단순 연결 리스트(Singly-Linked List)

 

3.1 단순 연결리스 구현

• List Interface

// List 인터페이스

public interface List<T> {
	
	// 첫번째에 노드 삽입
	void addFirst(T data);
	
	// 마지막에 노드 삽입
	void addLast(T data);
	
	// 노드 삽입
	void add(int index, T data);
	
	// 리스트 사이즈
	int size();
	
	// 입력받은 인덱스 노드의 값 반환
	T get(int index);
	
	// 입력받은 값의 node가 있는지 true, false 반환
	boolean contains(T data);
	
	// 첫번째 노드 삭제
	void removeFirst();
	
	// 마지막 노드 삭제
	void removeLast();
	
	// 입력받은 인덱스 노드 삭제
	void remove(int index);
	
	// 입력받은 데이터에 해당하는 노드 삭제
	void remove(T data);
}

• Node 정의 

	// 노드 클래스 정의
	private static class Node<T> {
		private T data; // 노드가 저장하는 데이터
		
		private Node<T> next; // 다음 노드를 가리키는 참조

		public Node(T data) {
			this.data = data;
			this.next = null;
		}
	}

---

• 0 번째 Node 삽입하는 메소드

	public void addFirst(T data) {
		Node<T> newNode = new Node<>(data);
		
		if (head == null) {
			head = newNode;
		} else {
			newNode.next = head;
			head = newNode;
		}
		
		size++;
	}

---

• 마지막 Node 삽하는 메소드

	// 마지막 값 삽입
	@Override
	public void addLast(T data) {
		Node<T> newNode = new Node<>(data);
		
		if (head == null) {
			head = newNode;
		} else {
			Node<T> lastNode = this.search(size - 1);
			
			lastNode.next = newNode;
		}
		
		size++;
	}

---

• 입력받은 인덱스에 Node를 삽입하는 메소드

	public void add(int index, T data) {
		if(index < 0 || index > size){
			throw new IndexOutOfBoundsException();
		}
		
		if(index == 0) {
			this.addFirst(data);
			
			return;
		}
		
		if(index == size) {
			this.addLast(data);
			
			return;
		}
		
		Node<T> newNode = new Node<>(data);
		Node<T> prevNode = this.search(index - 1);
		
		newNode.next = prevNode.next;
		prevNode.next = newNode;
		
		size++;
		
	}

---

• 현재 List의 Size를 반환하는 메소드

	@Override
	public int size() {
		
		return this.size;
	}

---

• 입력받은 인덱스 노드의 값 반환하는 메소드

	@Override
	public T get(int index) {
		if(index < 0 || index >= size) {
			throw new IndexOutOfBoundsException();
		}
		
		return this.search(index).data;
	}

---

• 입력받은 값의 node가 있는지 true, false 반환하는 메소드

	@Override
	public boolean contains(T data) {
		Node<T> current = head;
		
		while(current != null) {
			if(current.data.equals(data))
				return true;
			
			current = current.next;
			
		}
		return false;
	}

---

• 0번째 인덱스의 Node 삭제하는 메소드

	@Override
	public void removeFirst() {
		if(head ==null) {
			return;
		}else {
			Node<T> first = head;
			
			head = first.next;
			
			first.data = null;
			first.next = null;
			
			size--;
		}
		
	}

---

• 마지막 인덱스의 Node를 삭제하는 메소드

	@Override
	public void removeLast() {
		if(head == null) {
			return;
		}else if((size - 2) <= 0){
			this.removeFirst();
			
			return;

		}else {
			Node<T> lastPrevNode = this.search(size-2);
			
			lastPrevNode.next.data = null;
			lastPrevNode.next = null;
			
			size --;
		}
	}

---

• 입력받은 인덱스의 Node를 삭제하는 메소드

	public void remove(T data) {
		
		Node<T> current = head;
		
		if(current == null) {
			return;
		}
		
		if(current.data.equals(data)) {
			this.removeFirst();
			
			return;
		}
		
		for(int i = 0; i < size - 1; i++) {
			if(current.next.data.equals(data)) {
				Node<T> nextNode = current.next;
				
				current.next = nextNode.next;
				nextNode.data = null;
				nextNode.next = null;
				
				size--;
				
				break;
				
			}
			
			current = current.next;
		}
		
	}

---

• 입력받은 값의 List의 인덱스를 통해 값을 반환하는 메소드

	private Node<T> search(int index) {
		Node<T> node = head;
		
		for (int i = 0; i < index; i++) {
			node = node.next;
		}		
		
		return node;
	}

---

• List를 출력하는 메소드

	@Override
	public String toString() {
		Node<T> current = head;
		StringBuilder sb = new StringBuilder();
		
		sb.append("[");
		
		while(current != null) {
			sb.append(current.data + ", ");
			
			current = current.next;
		}
		
		if (sb.lastIndexOf(",") != -1) {
			sb.replace(sb.lastIndexOf(","), sb.length(), "]");			
		} else {
			sb.append("]");		
		}

		return sb.toString();
	}

 

3.2 단순 연결리스 테스트

• SinglyLinkedList 테스트

		List<String> list = new SinglyLinkedList<>();
		
		System.out.println(list);
		System.out.println("size : " + list.size());
		System.out.println();

---

• addFirst() 메소드 테스트

		list.addFirst("딸기");
		
		System.out.println(list);
		System.out.println("size : " + list.size());
		System.out.println();

---

• addLast() 메소드 테스트

		list.addLast("포도");
		list.addLast("키위");
		
		System.out.println(list);
		System.out.println("size : " + list.size());
		System.out.println();

 

---

• add() 메소트 테스트

		list.add(0, "수박");
		list.add(4, "바나나");
		
	
		System.out.println(list);
		System.out.println("size : " + list.size());
		System.out.println();

---

• get() 메소드 테스트

		System.out.println(list.get(0));
		System.out.println(list.get(1));
		System.out.println(list.get(3));
		System.out.println(list.get(6));
		System.out.println();

---

• removeFrist() 메소드 테스트

		list.removeFirst();
		
		System.out.println(list);
		System.out.println("size : " + list.size());
		System.out.println();

 

---

• removeLast() 메소드 테스트

		list.removeLast();
		
		System.out.println(list);
		System.out.println("size : " + list.size());
		System.out.println();

---

• remove() 메소드 테스트 (입력값 인덱스)

		list.remove(1);
		
		System.out.println(list);
		System.out.println("size : " + list.size());
		System.out.println();

---

• remove() 메소드 테스트 (입력값 값)

		list.remove("키위");
		System.out.println(list);
		System.out.println("size : " + list.size());
		System.out.println();

---

• contains() 메소드 테스트

		System.out.println(list);
		
		System.out.println(list.contains("딸기"));
		System.out.println(list.contains("두리안"));
		System.out.println(list.contains("바나나"));
		System.out.println(list.contains("참외"));
		System.out.println();