[ 알고리즘 ] 2. 연결리스트

📌 연결리스트의 특징 

연결리스트는 배열과는 거의 정반대의 특징을 가지고 있다.

 

🍉 k번째 원소를 확인/변경 하기 위해 O(n)가 필요함

: 배열과는 다르게 연결리스트에는 인덱스가 존재하지 않으므로, 임의의 위치에 있는 원소를 찾기 위해서는 첫원소부터 차례대로 거쳐서 원소를 찾아야 하므로 O(n)의 시간이 필요하다.

🍉 임의의 위치에 원소를 추가/제거 할때는 O(1)이 필요함 

: 배열은 연속된 메모리상에 위치하지만, 연결리스트는 다음 원소의 주소만 안다면 연속된 메모리 상에 위치하지 않아도 되므로, 중간에 원소를 추가/제거 할경우, 원소의 주소값만 넣어주면 되기때문에 O(1) 이라는 시간이 걸린다.

연결리스트의 제일 큰 장점이 된다.

🍉메모리 상에 연속한 구간이 필요하지 않아서 할당에 제약이 없다.

📌 연결리스트의 종류

https://blog.encrypted.gg/932?category=773649

🍉 단일 연결 리스트 : 각 원소가 자신의 다음원소의 주소를 가지고 있다.

🍉 이중 연결 리스트 : 각 원소가 자신의 다음,이전 원소의 주소를 가지고있다. 대신 주소값을 하나 더 가지니 메모리를 더 쓴다는 단점을 가지게 된다. 

🍉 원형 연결 리스트 : 첫번째 원소와 끝 원소가 연결되어있는 연결리스트

 

 

📌 구현 

🍉 Node 클래스 

class ListNode {
	private String data;
	public ListNode link;
	
	public ListNode() {
		this.data = null;
		this.link = null;
	}
	
	public ListNode(String data) {
		this.data = data;
		this.link = null;
	}
	public ListNode(String data,ListNode link) {
		this.data = data;
		this.link = link;
	}
	public String getData() {
		return this.data;
	}
}

 

🍉 구성 

public class LinkedList {
	
	private ListNode head;
	
	public LinkedList() {
		head = null;
	}
	public void insertNode(ListNode preNode, String data) { //중간에 삽입 
	}
	public void insertNode (String data) { // 마지막에 삽입 
	}
	public void deleteNode (String data) { // 중간노드 삭제 
	}
	public void deleteNode( ) {// 마지막 노드 삭제 
	}
	public void printList() {
	}
	public static void main(String args[]) {
	}
}

 

🍉 insertNode ( 중간에 삽입 ) 

public void insertNode(ListNode preNode, String data) { //중간에 삽입 
		ListNode newNode = new ListNode(data);
		
		newNode.link = preNode.link;
		preNode.link = newNode;
	}

앞의 노드 preNode의 link를 newNode의 link에 주고 

preNode의 link에 newNode를 꽂아준다. 

 

🍉 insertNode ( 마지막에 삽입 ) 

public void insertNode (String data) { // 마지막에 삽입 
		ListNode newNode = new ListNode(data);
		if (head == null) 
			this.head = newNode;
		else {
			ListNode tempNode = head;
			while (tempNode.link != null) {
				tempNode = tempNode.link;
			}
			// 마지막 노드의 link가 다음 노드를 참조하도록 함 
			tempNode.link = newNode;
		}
	}

마지막노드 일때까지 ( 마지막 원소의 link가 null 일때 ) 접근한 후 새로운 노드를 연결해줌 

 

🍉  deleteNode( 중간노드 삭제 ) 

	public void deleteNode (String data) { // 중간노드 삭제 
		ListNode preNode = head;
		ListNode tempNode = head.link;
		
		//데이터가 일치하면 
		if (data.equals(preNode.getData())) {
			head = preNode.link;
			preNode.link = null;
			
		}else {
			while (tempNode != null) {
				if (data.equals(tempNode.getData())) {
					if (tempNode.link == null) {
						preNode.link =null;
					}
					else {
						preNode.link = tempNode.link;
						tempNode.link = null;
					}
					break;
				}
				else {
					// 데이터가 일치하지 않을 경우
					preNode = tempNode;
					tempNode = tempNode.link;
				}
			}
		}
	}

🍉  deleteNode( 마지막노드 삭제 ) 

	public void deleteNode( ) {
		ListNode preNode;
		ListNode tempNode;
		
		// head가 null인경우는 모든노드가 삭제된 경우
		if (head == null) {
			return;
		}
		if (head.link == null) {
			head = null;
		}
		else {
			preNode = head;
			tempNode = head.link;

			while (tempNode.link != null) { // 끝까지 간다
				preNode = tempNode;
				tempNode = tempNode.link;
			}
			preNode.link = null;
		}
	}

🍉  searchNode( 노드 탐색 ) 

public ListNode searchNode (String data) {
		ListNode tempNode = this.head;
		
		while (tempNode !=null) {
			if (data.equals(tempNode.getData())) {
				return tempNode;
			}
			else {
				tempNode = tempNode.link;
			}
		}
		return tempNode;
	}