자료구조_선형구조 ②연결리스트 LinkedList

 

 

[1] 연결 리스트 구성 

---

(1) 노드

• 리스트의 원소 

(2) 포인터 변수

• 메모리 공간의 주소를 저장하는 변수 

(3)구조체

• 여러개의 변수를 묶어서 만든 자료형 
• C언어, C#언어에 존재 , JAVA는 구조체 정의가 없다 

(4) 연결리스트 개요 

• 데이터 삽입, 삭제를 포인트 조작으로 가능하다 
• 자료를 저장하는 노드에는 자료와 다음 요소를 가리키는 링크(포인터)가 있음
• 자료가 추가 될때 노드 만큼의 메모리를 할당 받고 이전 노드의 링크로 연결함 (정해진 크기가 없음)
• 기존 데이터 변경없이 노드를 추가할수 있다
• 데이터 삽입시 사용 공간의 오버플로가 없다 
• 헤드부터 링크를 따라가며 검색한다 

• 동일한 데이터 타입을 순서에 따라 관리하는 자료 구조

 

 

[2] 연결 리스트 종류

---

(1) 단순 연결 리스트

 

• 전진검색만 가능하다
• 처음부터 검색해야하므로 검색시간이 많이 소요된다
• 삽입/삭제시 이전 노드를 알고 있어야 링크 주소를 변경할수 있다 
• 이전노드를 알고 있어야 삽입/삭제가 가능하다 
• 삽입방법 : 삽입할 노드 링크에 이전노드의 링크를 할당한다 -> 이전 노드의 링크에 삽입할 노드의 주소를 할당한다 
• 삭제방법 : 삭제할 노드의 이전노드의 링크에 삭제할 노드의 링크를 할당한다 

 

 

(2) 원형 연결 리스트

마지막 노드의 링크에 첫 노드의 주소를 지시하게 하여 이어지게 한 형태 

첫노드를 삽입할때 마지막 노드의 링크도 변경해야한다 

구조를 순회할수 있어 데이터를 쉽게 삽입 ,삭제가 가능하지만 순회하는 구조때문에 순차적으로 탐색해야한다 

 

 

(3) 이중 연결 리스트

노드가 data, llink, rlink 3개의 필드로 구성되어있다. 

정방향, 역방향 검색이 가능하다

삽입방법 : 새 노드의 llink에 노드a의 주소를 할당 , 새 노드의 rlink에 노드 b의 주소를 할당, 노드 a의 rlink에 새 노드의 주소 할당 , 노드 b의 llink에 새 노드의 주소 할당

삭제방법 : b노드의 rlink를 이전노드의 rlink에 할당 , b노드의 llink를 다음 노드의 llink에 할당 

한방향으로만 링크를 통해 이동이 가능했는데 좌우 모두 링크가 존재하여 양방향으로 이동이 가능하다

탐색 및 데이터 관리 시간을 단축할수 있다 

데이터data

왼쪽 링크 llink

오른쪽링크 rlink

 

Doubly LinkedList (데이터 보관 장소)
head	→	1번 Node	↔	2번 Node	↔	3번 Node	↔	4번 Node
		데이터 A 2번 노드 주소값을 가지고 있음		데이터 B 1,3번 노드 주소값을 가지고 있음		데이터 C 2,4번 노드 주소값을 가지고 있음		데이터 D 3,5번 노드 주소값을 가지고있음

 

 

(4)이중 원형 연결 리스트

원형연결리스트와 이중연결리스트를 결합했다 

연결리스트 중 가장 복잡한 형태 

순방향, 역방향 검색 가능하다 

중간에 노드가 끊기더라도 나머지 노드에 접근가능

 

 

 

[3] 연결 리스트 시간복잡도

---

 

(1) 시간복잡도 O(n)

 

 

 

 

[4] LinkedList 구현

---

원리를 이해하자 

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 class MyLinkedList {

	private MyListNode head;
	int count;
	
	public MyLinkedList()
	{
		head = null;
		count = 0;
	}
	
	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)  //다음로드가 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;
	}
	
	public String getElement(int position)
	{
		int i;
		MyListNode tempNode = head;
		
		if(position >= count ){
			System.out.println("검색 위치 오류 입니다. 현재 리스트의 개수는 " + count +"개 입니다.");
			return new String("error");
		}
		
		if(position == 0){  //맨 인 경우

			return head.getData();
		}
		
		for(i=0; i<position; i++){
			tempNode = tempNode.next;
			
		}
		return tempNode.getData();
	}

	public MyListNode getNode(int position)
	{
		int i;
		MyListNode tempNode = head;
		
		if(position >= count ){
			System.out.println("검색 위치 오류 입니다. 현재 리스트의 개수는 " + count +"개 입니다.");
			return null;
		}
		
		if(position == 0){  //맨 인 경우

			return head;
		}
		
		for(i=0; i<position; i++){
			tempNode = tempNode.next;
			
		}
		return tempNode;
	}

	public void removeAll()
	{
		head = null;
		count = 0;
		
	}
	
	public int getSize()
	{
		return count;
	}
	
	public void printAll()
	{
		if(count == 0){
			System.out.println("출력할 내용이 없습니다.");
			return;
		}
		
		MyListNode temp = head;
		while(temp != null){
			System.out.print(temp.getData());
			temp = temp.next;
			if(temp!=null){
				System.out.print("->");
			}
		}
		System.out.println("");
	}
	
	public boolean isEmpty()
	{
		if(head == null) return true;
		else return false;
	}
	
}

 

 

public class MyLinkedListTest {

	public static void main(String[] args) {

		MyLinkedList list = new MyLinkedList();
		list.addElement("A");
		list.addElement("B");
		list.addElement("C");
		list.printAll();
		list.insertElement(3, "D");
		list.printAll();
		list.removeElement(0);
		list.printAll();
		list.removeElement(1);
		list.printAll();
						
		list.insertElement(0, "A-1");
		list.printAll();
		System.out.println(list.getSize());
		
		list.removeElement(0);
		list.printAll();
		System.out.println(list.getSize());
		
		list.removeAll();
		list.printAll();
		list.addElement("A");
		list.printAll();
		System.out.println(list.getElement(0));
		list.removeElement(0);
	}
}

 

 

노드 추가하기 

 

---

void insert(int data) {
    node *ptr;
    node * newNode = (node*)malloc(sizeof(node));   
    
    newNode->data = data;        
    newNode->next = NULL;

    if (head == NULL) {           
        head = newNode;
    } else {
        if (head->data > newNode->data) {
            newNode->next = head;
            head = newNode;
            return;
        }
        for (ptr = head; ptr->next; ptr = ptr->next) {      
            if (ptr->data < newNode->data && ptr->next->data > newNode->data) {
                newNode->next = ptr->next;
                ptr->next = newNode;
                return;
            }
        }
        ptr->next = newNode;                 
    }
}

 

 

 

데이터 삭제 

---

 

맨앞 : 링크가 null을 가리키게 한뒤에 메모리를 삭제한다 

맨뒤 : 마지막 노드를 가르켰던 이전 노드를 prev 찾아 null로 가리키게 한뒤에 메모리를 삭제한다 

 

int deleteNode(int data) {
    node * cur, *prev;
    cur = prev = head;
    
    if (head == NULL) {
        printf("ERROR : List is Empty!\n");
        return -1;
    }

    if (head->data == data) {             
        head = cur->next;
        cur->next = NULL;
        free(cur);
        return 1;
    }
    
    for (; cur; cur = cur->next) {            
        if (cur->data == data) {
            prev->next = cur->next;
            cur->next = NULL;
            free(cur);
            return 1;
        }
        prev = cur;
    }

    printf("ERROR : There is no %d!\n", data);
    return -1;
}

 

노드를 찾을때 

---

int search_list(int data){
    Node* ptr;
    for(ptr = head ; ptr ; ptr=ptr->next){
        if(ptr->data == data){ 
            return 1;
        }
    }
    
    return -1;
}

 

 

시간복잡도

---

 

시간 복잡도 Big O 표기법 이란 

불필요한 연산을 제거하여 알고리즘 분석을 쉽게 할 목적으로 사용된다 

 

Bio O 표기법	내용	시간복잡도 빠른순
O(1)	입력자료의 수에 관계없이 일정한 실행시간을 갖음	1
O(logn)	입력자료의 수에 따라 시간이 흐를수록 시간이 조금씩 증가	2
O(n)	입력 자료의 수에 따라 선형적인 실행 시간이 걸리는 경우 - 입력자료마다 일정 시간 할당	3
O(nlogn)	큰 문제를 일정 크기 갖는 문제로 쪼개고(logn+logn+ .. + logn) 다시 그것을 모으는 경우	4
O(n^2)	이중 루프내에서 입력 자료를 처리할 때	5
O(n^3)	삼중 루프 내에서 입력자료 처리할 때	6
O(2^n)		7
O(n!)		8

 

데이터 변경이 용이하여 자료를 변경할때 주소를 지우고 값을 지우면 끝나는 단순한 구조이다 : O(1)

검색은 노드의 링크를 따라서 순차적으로 가장 마지막에 노드로 접근해야한다  : O(n) 

 

 

연결리스트 의 시간복잡도	삽입 add	O(1)
	삭제	O(1)
	검색 find	O(n)