2) LinkedList 링크드리스트

* 타 블로그 글이 아닌 독학을 통해 이해한 내용을 작성한 것이기 때문에 , 지적은 성대히 환영합니다 ! *

 

 

링크드리스트 LinkedList 에 대하여 알아보겠다.

 

링크드리스트와 배열의 가장 큰 차이는 논리적과 물리적 위치가 다르다는 것이다.

 

선형구조이고 , 자료가 추가 될 때 마다 추가로 메모리를 할당 받는다.

 

그렇기 때문에 위치가 다를 수 있다.

 

링크드리스트의 장점은 추가나 삭제의 비용이 적다는 것이다.

 

단점은 검색 탐색의 비용이 높다는 점 이다.

 

LinkedList 에서 맨 앞의 노드를 헤드라 칭한다. 

 

 

 

 

 

 

 

각 노드(요소) 간에 링크로 연결되어 있으며 요소를 추가 할 땐 들어갈 위치 앞의 요소 (전 노드)를 알아야한다.

 

먼저 MyListNode 클래스다.

public class MyListNode {

	private String data;       // 자료
	public MyListNode next;    // 다음 노드를 가리키는 링크
	
	public MyListNode(){
		data = null;
		next = null;
	}
	
	public MyListNode(String data){
		this.data = data;
		this.next = null;
	}
	
	public MyListNode(String data, MyListNode link){
		this.data = data;
		this.next = link;
	}
	
	public String getData(){
		return data;
	}
}

 

 

다음 코드는 헤드가 없을 시 맨 앞에 , 아니면 노드의 맨 끝에 삽입하는 코드이다.

 

 

public MyListNode addElement( String data )
	{
		
		MyListNode newNode;
		if(head == null){  //맨 처음일때
			newNode = new MyListNode(data);
			head = newNode;
		}
		else{
			newNode = new MyListNode(data);
			MyListNode temp = head;
			while(temp.next != null)  //맨 뒤로 가서  
				temp = temp.next;
			temp.next = newNode;
		}
		count++;
		return newNode;
	}

 

만약 헤드가 없다면 추가 될 값은 링크드리스트의 맨 앞에 위치한다.

 

그렇지 않다면 , 추가될 값은 노드의 맨 끝에 위치한다.

 

 

값을 중간에 위치하고 삭제할땐 

 

전 노드의 위치를 찾아서 링크를 연결해주는 식으로 짜면 된다.

 

 

public MyListNode insertElement(int position, String data )
	{
		int i;
		MyListNode tempNode = head;
		MyListNode newNode = new MyListNode(data);
		
		if(position < 0 || position > count ){
			System.out.println("추가 할 위치 오류 입니다. 현재 리스트의 개수는 " + count +"개 입니다.");
			return null;
		}
		
		if(position == 0){  //맨 앞으로 들어가는 경우
			newNode.next = head;
			head = newNode;
		}
		else{
			MyListNode preNode = null;	
			for(i=0; i<position; i++){
				preNode = tempNode;
				tempNode = tempNode.next;
				
			}
			newNode.next = preNode.next;
			preNode.next = newNode;
		}
		count++;
		return newNode;
	}

 

public MyListNode removeElement(int position)
	{
		int i;
		MyListNode tempNode = head;
		
		if(position >= count ){
			System.out.println("삭제 할 위치 오류입니다. 현재 리스트의 개수는 " + count +"개 입니다.");
			return null;
		}
		
		if(position == 0){  //맨 앞을 삭제하는
			head = tempNode.next;
		}
		else{
			MyListNode preNode = null;	
			for(i=0; i<position; i++){
				preNode = tempNode;
				tempNode = tempNode.next;
			}
			preNode.next = tempNode.next;
		}
		count--;
		System.out.println(position + "번째 항목 삭제되었습니다.");
		
		return tempNode;
	}