티스토리 뷰

베니의 자료구조 - 단순 연결 리스트(Linked List)

베니는 생활코딩 이고잉님의 자료구조 강의, 구글링을 통해 자료구조를 공부하고 있습니다.  
인용하는 내용의 출처는 링크를 남겨놓고 있습니다.
도움 주신 모든분들께 감사드립니다!

생활코딩 이고잉님 , 초보몽키님의 개발공부로그  

 

목차

1. 정의

2. 특징

3. 활용

4. 베니의 생각

 

Linked List는 데이터와 다음 데이터와 연결해주는 공간이 존재합니다.


1. 정의

데이터가 있는 Data field와 데이터와 데이터를 연결하는 Link field를 하나의 객체로 볼 때
이것을 Node라고 하며 Node들로 이루어진 List가 Linked List입니다.

생활코딩 이고잉님의 강의에 있는 이미지 ( Linked List의 구조를 한 눈에 쉽게 볼 수 있습니다!  )


2. 특징

(1) 첫번째 노드를 나타내는 head라는 변수가 존재한다.

Array List의 경우 첫번째 인덱스는 [0]이지만 Linked List는 head를 통해 첫번째 노드를 가리키고 있습니다.

 

(2) 메모리의 공간 사용이 연속적이지 않다.

Array List는 메모리의 공간이 할당 될 때 연속적이지만 Linke List는 공간 할당이 흩어져 있으나

Link field를 통해 서로 연결되어 있습니다.

 

(3) Element의 삽입과 삭제가 빠르다.

Array List는 Element를 삽입할 때와 삭제할 때 해당 Element의 뒤에 있는 Element들을 모두 이동해야 하지만

Linked List는 노드를 삽입할 때 해당 위치 전의 Node의 Link field에 삽입할 노드를 가리키게 하고

삽입할 노드의 Link filed에 다음 노드를 가리키게 하면 됩니다.

( 글로 설명하려니 가독성이 좋지 않은데 활용을 통해 더 쉽게 이해하실 수 있으실 것입니다! )

 

 


3. 활용

(1) Linked List 사용법

Linked List를 자바에서 import해서 가져와서 사용하는 것만이 아닌 이고잉님께서 수업하신 것처럼

LinkedList라는 클래스와 Main 클래스를 만들어 직접 구현해보았습니다!

 

먼저 LnkedList의 기본 구성만 구현한 클래스입니다.

public class LinkedList {
    private Node head; // 첫번째 노드를 나타낼 head
    private Node tail; // 마지막 노드를 나타낼 tail
    private int size = 0; // 노드의 갯수를 나타낼 size
    
    private class Node{
    	private Object data; // 노드의 데이터가 담길 data
        private Node next;   // 다음 노드에 대한 정보가 담길 next
        
        // Node 객체의 데이터를 담을 생성자
        public Node(Object input){
            this.data = input;
            this.next = null;
        }
        
        // 편리한 디버깅을 위해 Node를 출력 시 data가 나올 수 있도록 세팅
        public String toString(){
        	return String.valueOf(this.data);
        }
    }

}

그리고 메인에서 LinkedList를 사용하는 것을 보여줄 클래스 입니다.

// LinkedList 클래스를 사용한 결과들을 보여줄 메인 클래스
public class Main {

    public static void main(String[] args {
    	LinkedList numbers = new LinkedList(); // ArrayList와 사용 방식은 동일합니다.
    }

}

 

(2) addFirst

단순 연결리스트의 가장 앞 즉 head 부분에 노드를 추가하는 addFirst를 먼저 구현해보도록 하겠습니다.

보기 쉽게 LinkedList의 클래스 안에 메서드 구현 부분만 코드 블럭으로 보여드리도록 하겠습니다.

public void addFirst(Object input) {
    Node newNode = new Node(input); // input 값으로 Node를 인스턴스화 하여 newNode를 초기화
    newNode.next = head;	// 기존의 head 값은 newNode 객체의 next 변수가 되고
    head = newNode;		// newNode 객체는 새로운 head가 됩니다
    size++;			// 새로운 노드가 생겼으니 size를 증가시켜줍니다

    if(head.next == null){  // head의 next값이 null이라는 의미는 현재 head가 마지막 노드라는 의미이므로
    	tail = head;	// head의 값이 tail이기도 하다는 뜻이기도 합니다
    }
}

위에 addFirst 메서드를 그림으로 한 번 보도록 하겠습니다.

첫 addFirst 메서드 실행 시 플로우입니다

그림으로 한 번 그려 보았는데 이거 하나 그리는데시간이 너무 걸렸습니다... ㅜㅜ

 

1. input 값을 받아 Node 클래스의 생성자를 통해 Node 객체가 완성되며 newNode라는 변수로 인스턴스화되었습니다.

2. 첫 addFirst 시에는 head는 null이며 newNode.next는 null을 나타내게 됩니다.

3. head는 newNode 객체를 가리키게 되며

4. 노드가 추가되었으니 사이즈가 1개 상승하고

5. 마지막으로 head.next가 null이면 tail 또한 newNode를 가리키게 됩니다.

 

그리고 addFisrt를 다시 실행한다면

두번째 실행부터는 위와 같이 동작한다

위 그림과 같이 동작하며 빨간색 부분은 첫번째 addFirst의 객체를 의미합니다.

 

numbers.addFirst(30); // [30]
numbers.addFirst(20); // [20, 30]
numbers.addFirst(10); // [10, 20, 30]

 

LinkedList 클래스에서 addFirst 메서드를 구현한 후 Main 클래스에서 numbers.addFirst 실행시 

마지막에 사용한 메서드값이 가장 앞에 오게 되므로 10, 20, 30 이렇게 나열되게 됩니다.

 

 

(3) addLast

addFirst가 head에 추가하는 메서드였다면 addLast는 tail에 추가되는 메서드입니다.

public void addLast(Object input){
    Node newNode = new Node(input); 
    
    // 기존에 데이터가 존재하지 않을 때는
    if(size == 0){
        addFirst(input);    // 데이터를 앞에 넣으나 뒤에 넣으나 같은 결과를 나타냅니다
    } else {
    	tail.next = newNode; // tail의 next는 마지막 값이 되고
        tail = newNode;	// tail은 newNode를 가리키게 되며
        size++;	// Element 크기 증가로 마무리합니다.
    }
    
}

가장 마지막 노드 뒤에 새로운 노드를 연결하고 꼬리(tail)는 새로운 노드를 가리키게 만들면

마지막 노드는 새로 추가한 노드가 되며 Element 크기가 증가함으로 정상적으로 addLast가 작동합니다.

numbers.addLast(10); // [10]
numbers.addLast(20); // [10, 20]
numbers.addLast(30); // [10, 20, 30]

addLast 실행 시 맨 뒤에 노드가 추가되는 것을 확인할 수 있습니다.

 

(4) node

node( )는 index를 인자값으로 받아서 index에 위치한 노드의 데이터를 가져오는 메서드입니다. 

Node node(int index){
    Node x = head; // 가장 첫번째 index인 head의 값부터 시작하여
    
    for(int i=0; i < index; i++){ // index 크기만큼
        x = x.next; // 다음 노드를 x에 할당 
    }
    return x; // 노드 출력
}
numbers.addLast(10); // [10]
numbers.addLast(20); // [10, 20]
numbers.addLast(30); // [10, 20, 30]
System.out.println(numbers.node(2)); // 30이 출력됩니다.

(5) add

add( )는 index와 data를 인자값으로 받아서 List에서 우리가 원하는 위치에 Element를 추가하는 메서드입니다.

// 노드를 추가할 위치를 나타내는 k와 노드의 data인 input을 받습니다.
public void add(int k, Object input){
	if(k == 0){  // 노드를 추가할 위치의 index 0일 때는
        addFirst(input); // 맨 앞에 노드를 추가하는 것이므로 addFirst 메서드를 사용합니다.
    } else {
        Node temp1 = node(k-1); // 우선 노드를 넣을 위치의 전 노드를 알아야 합니다.
        Node temp2 = temp1.next; // 전 노드의 next 즉 노드를 넣을 위치에 현재 있는 노드입니다.
        Node newNode = new Node(input); // 새로운 노드 객체를 만들고
        temp1.next = newNode;  // 전 노드의 next를 새로운 노드로 연결하고
        newNode.next = temp2;  // 새로운 노드의 next를 노드를 넣을 위치에 있었던 노드로 연결합니다.
        size++;	// 사이즈 증가
        if(newNode.next == null){ // 새로운 노드의 next가 null일 때 ( 새로운 노드가 마지막 노드일 때 )
        	tail = newNode; // 새로운 추가된 노드는 꼬리가 됩니다.
        }
    }
}

add() 메서드는 그 전에 알아본 메서드들보다 좀 더 복잡한 편이며 그만큼 플로우를 정확히 알아둘 필요가 있습니다.

numbers.addLast(10); // [10]
numbers.addLast(20); // [10, 20]
numbers.addLast(30); // [10, 20, 30]
numbers.add(2, 25);  // [10, 20, 25, 30]
numbers.add(2, 23);  // [10, 20, 23, 25, 30]
numbers.add(0, 5);   // [5, 10, 20, 23, 25, 30]

add를 실행 시 위와 같이 노드들이 나열되게 됩니다.

 

(6) toString

toString()은 데이터를 쉽게 확인할 수 있도록 시스템 출력의 형식을 변경할 수 있습니다.

public String toString(){
    if(head == null){ // head가 null이면 값이 없으므로
        return "[]";  // 빈 값 출력
    } 
    
    Node temp = head; // temp는 첫번째 노드를 가리키고
    String str = "[";
    
    while(temp.next != null){ // 다음 값이 null이 되기 전까지 반복
       str += temp.data + ", "; // temp의 data에 콤마를 추가하여 str에 추가하며
       temp = temp.next;		// temp는 temp의 다음 노드를 가리키게 됩니다.
    }
    
    str += temp.data; 			// 마지막 노드의 data를 출력에 문자열에 추가
    
    return str + "]";			// 닫아주는 문자열을 추가하며 출력
}

위와 같이 toString 메서드를 오버라이딩 해준 후 출력하면

numbers.addLast(10); // [10]
numbers.addLast(20); // [10, 20]
numbers.addLast(30); // [10, 20, 30]
numbers.add(2, 25);  // [10, 20, 25, 30]
numbers.add(2, 23);  // [10, 20, 23, 25, 30]
numbers.add(0, 5);   // [5, 10, 20, 23, 25, 30]

System.out.print(numbers); // [5, 10, 20, 23, 25, 30] 이렇게 출력이 됩니다!

List의 데이터를 확인 시 편리하게 되었습니다~!

 

(7) removeFirst

removeFirst는 가장 첫번째 노드를 삭제하는 메서드이고

삭제를 진행 후에 노드가 가지고 있던 값을 리턴하게 되어 있습니다.

public void removeFirst(){
	Node temp = head; // head를 temp에 할당 후
    head = head.next; // head의 next 노드를 head에 할당한다
    Object returnData = temp.data; // 삭제될 temp 노드의 data를 출력 값으로 따로 빼둔 후
    temp = null;	// temp를 null로 초기화!
    size--;			// 사이즈도 1 줄이고
    retrun returnData;	// 삭제한 노드의 데이터 출력
}

메서드를 사용했을 때 노드의 변화를 살펴보겠습니다.

numbers.addLast(10); // [10]
numbers.addLast(20); // [10, 20]
numbers.addLast(30); // [10, 20, 30]
numbers.removeFirst();	// 10 출력

System.out.print(numbers); // [20, 30] 이렇게 출력이 됩니다!

(8) remove, removeLast

자 이제 원하는 index의 노드를 삭제할 수 있는 remove 메서드를 구현해보겠습니다.

public Object remove(int k){
    if(k == 0){	 // 첫번째 노드를 삭제 할 때는
        return removeFirst(); // removeFirst 메서드를 사용합니다
    }
    Node temp = node(k-1);  // 삭제하려는 노드의 전 노드를 알아내고
    Node todoDeleted = temp.next;	// 삭제하려는 노드를 따로 저장해둡니다.
    temp.next = temp.next.next;	// 삭제하려는 위치 다음의 노드를 전 노드의 다음으로 연결 후
    Object returnData = todoDeleted.data; // 삭제하는 노드를 리턴할 데이터로 저장합니다.
    if(todoDeleted == tail){	// 삭제하려는 노드가 tail이었을 때는
    	tail = temp;	// tail이 삭제할 노드의 전 노드가 되게 합니다.
    }
    todoDeleted = null;	// 의미가 있진 않지만 삭제한다는 느낌을 쇽!
    size--; // 갯수를 줄이고
    
    return returnData; // 삭제한 노드의 data를 리턴합니다.
}

메서드를 구현했으니 삭제를 해보겠습니다!

numbers.addLast(10); // [10]
numbers.addLast(20); // [10, 20]
numbers.addLast(30); // [10, 20, 30]
numbers.remove(1);	// 20 출력

System.out.print(numbers); // [10, 30] 이렇게 출력이 됩니다!

이어서 removeLast도 진행해보겠습니다!

public Object remoeLast() {
   return remove(size-1);	// size-1은 마지막 노드의 인덱스를 의미합니다. 
}

만들어 놓은 remove 메서드를 통해 쉽게 구현할 수 있었습니다. 간단하쥬?

자 실제로 작동 테스트를 해봅니다.

 

numbers.addLast(10); // [10]
numbers.addLast(20); // [10, 20]
numbers.addLast(30); // [10, 20, 30]
numbers.removeLast();	// 30 출력

System.out.print(numbers); // [10, 20] 이렇게 출력이 됩니다~

remove는 이걸로 끝입니다~!

 

(9) size, get

size 메서드는 numbers의 노드가 몇 개인지 알려주는 메서드입니다.

public int size(){
    return size;
}

간단하니 좋네요 ㅋㅋ

바로 사용해보겠습니다~

numbers.addLast(10); // [10]
numbers.addLast(20); // [10, 20]
numbers.addLast(30); // [10, 20, 30]


System.out.print(numbers.size()); // 3이 출력이 됩니다~

get 메서드는 index를 통해 해당 노드의 값을 알려줍니다.

public Object get(int k){
    Node temp = node(k); // 인덱스 k에 맞는 노드를 temp 저장 후
    return temp.data;  // temp 노드의 data를 리턴합니다.
}

이번에도 간단합니다 ㅎㅎ

numbers.addLast(10); // [10]
numbers.addLast(20); // [10, 20]
numbers.addLast(30); // [10, 20, 30]


System.out.print(numbers.get(1)); // 20이 출력이 됩니다.

size와 get을 빠르게 알아보았습니다!

 

(10) indexOf

indexOf는 인자값으로 전달한 값과 같은 값을 가지고 있는 index를 반환합니다.

public int indexOf(Object data){
	Node temp = head; // data값과 같은 값을 찾기 위해 첫번째 노드부터 검색합니다.
    int index = 0;	// 초기 index 값은 0입니다.
    while(temp.data != data){ // data가 노드의 data와 같기 전까지
    	temp = temp.next;	// 다음 노드를 temp에 할당하고
        index++;	// index를 증가시킵니다.
        if(temp == null){	// 마지막 노드까지 반복을 했지만 같은 data를 못 찾았다는 뜻이므로
        	return -1;	// -1을 반환합니다.
        }
    }
    return index; // 같은 data를 찾을 경우 index를 반환합니다.
}
numbers.addLast(10); // [10]
numbers.addLast(20); // [10, 20]
numbers.addLast(30); // [10, 20, 30]

System.out.print(numbers.indexOf(20)); // 1이 출력이 됩니다.
System.out.print(numbers.indexOf(50)); // -1이 출력이 됩니다.

List에 data가 있으면 index를 반환하고 없다면 -1를 반환합니다.

 

(11) Iterator next

LinkedList에서도 ArrayList처럼 iterator를 통해 메서드를 사용할 수 있습니다.

public ListIterator listIterator(){ // listIterator 함수 실행 시
	return new ListIterator(); ListIterator를 인스턴스화 해서 반환
}

public class ListIterator{
    private Node next;	// 포인터 용도로 사용될 변수입니다.
    private Node lastReturned; // next() 메서드 실행 시 출력되는 노드입니다.
	private int nextIndex; // 포인터의 위치를 알려주는 값입니다.
    
	ListIterator(){	// 생성자를 통해 
    	next = head;	// 첫번째 노드를 next 변수에 할당합니다.
    }

	public Object next(){	// next 메서드는
    	lastReturned = next;	// next 노드를 리턴할 노드로 정하고
        next = next.next;	// 다음의 노드를 next로 할당한 후
        nextIndex++;	// 노드를 가리키는 포인터를 다음으로 이동시키고
        return lastReturned.data;	// 리턴할 노드의 데이터를 리턴합니다.
    }
}

좀 복잡해서 저도 한 번에 이해하기가 어려웠습니다.. 

몇 번 반복해서 생각하시고 값을 대입해 진행해보시면 이해하실 수 있으실 것입니다!

numbers.addLast(10);
numbers.addLast(20);
numbers.addLast(30);
LinkedList.ListIterator i = numbers.listIterator();
System.out.println(i.next()); // nextIndex가 0에서 1이 되고 lastReturned인 10을 출력합니다!
System.out.println(i.next()); // nextIndex가 2이 되고 lastReturned인 20을 출력합니다!
System.out.println(i.next()); // nextIndex가 3이 되고 lastReturned인 30을 출력합니다!

iterator 관련해서는 더 반복해서 학습을 하여 확실히 알아두면 좋을 것 같습니다!

 

(12) Iterator hasNext

hasNext는 next()를 더 실행할 수 있는지 다음 노드가 있는지 알려주는 메서드입니다.

public boolean hasNext(){
	return nextIndex < size(); // next가 null을 가리키는 경우 false를 리턴합니다.
}

ndexIndex가 size보다 작지 않다는 것은 lastReturned는 마지막 값을 가리키고 next는 null을 가리키고 있다는 것과 같습니다.

numbers.addLast(10);
numbers.addLast(20);
numbers.addLast(30);
LinkedList.ListIterator i = numbers.listIterator();
System.out.println(i.next());	// nextIndex가 0에서 1이 되고 lastReturned인 10을 출력합니다!
System.out.println(i.next());	// nextIndex가 2이 되고 lastReturned인 20을 출력합니다!
System.out.println(i.hasnext());	// nextIndex는 2이고 size는 3이므로 true를 반환합니다
System.out.println(i.next());	// nextIndex가 3이 되고 lastReturned인 30을 출력합니다!
System.out.println(i.hasnext());	// nextIndex는 3이고 size는 3이므로 false를 반환합니다

hasnext() 사용하여 다음 값이 있는지 체크를 완료하였고

이제는 Iterator를 통해 다음과 반복적인 작업들을 구현할 수 있게 되었습니다!

numbers.addLast(10);
numbers.addLast(20);
numbers.addLast(30);
LinkedList.ListIterator i = numbers.listIterator();
while(i.hasNext()){
	System.out.println(i.next()); // 10 20 30 이 줄바꿈이 되며 출력됩니다!
}

(13) Iterator add

Iterator로 순회하는 과정에서 데이터를 중간에 삽입하는 방법을 알아보겠습니다.

public void add(Object input){
    Node newNode = new Node(input);
    
    if(lastReturned == null){ // 노드가 없는 상태에서 첫번째 추가이면
    	head = newNode;	// 새로운 노드를 head로 가리키고
    	newNode.next = next;	// 새로운 노드의 next는 next 노드를 가리킵니다.
    } else {
    	lastReturned.next = newNode;	// 새로운 노드를 lastReturned의 next로 연결시키고
    	newNode.next = next;	// next는 새로운 노드의 next로 연결시킵니다.
    }
    lastReturned = newNode;	// 새로운 노드를 리턴할 노드로 정한 후
    nextIndex++;	// next의 index 증가와 
    size++;	// size도 증가시킵니다.
}

위에서 구현한 add 메서드를 가지고 추가를 해보도록 하겠습니다.

numbers.addLast(10); // [10]
numbers.addLast(20); // [10, 20]
numbers.addLast(30); // [10, 20, 30]
LinkedList.ListIterator i = numbers.listIterator();
i.add(5); // [5, (10), 20, 30] ()괄호는 현재 next변수가 가리키는 위치입니다.
i.next(); // [5, 10, (20), 30] lastReturned는 현재 10을 가리키고 있으며
i.add(15); // add를 다시 진행 시에는 lastReturned.next에 값이 추가되므로 [5, 10, 15, 20, 30]이 됩니다
System.out.println(numbers);

ㅎㅎㅎ.. 복잡합니다.. 저도 내용을 작성해놓고 다시 생각하면 까먹네요...

복습은 필수입니다!

 

(14) Iterator remove

이제 마지막으로 remove 메서드를 살펴보도록 하겠습니다.

public void remove(){
    if(nextIndex == 0){ // 삭제할 노드가 없을 경우
        throw new IllegalStateException(); // 예외 처리
    }
    
    LinkedList.this.remove(nextIndex-1); // lastReturned를 가리키기 위해 nextIndex를 이용합니다
    nextIndex--;
}

위에서 remove 메서드는 메서드 안에서 첫번째 노드부터 해당되는 노드를 찾을 때까지

반복문을 수행하므로 hasNext를 통해 반복문을 이미 사용하는 Iterator에서는 비효율적인 방법입니다.

 

꼭 한 번 어떤 방법이 더 효율적인지 생각을 해보는 시간을 갖도록 하겠습니다.

numbers.addLast(10); // [10]
numbers.addLast(20); // [10, 20]
numbers.addLast(30); // [10, 20, 30]
LinkedList.ListIterator i = numbers.listIterator();
while(i.hasNext()){
	if((int)i.next() == 20){
        i.remove();
    }
}

System.out.println(numbers); // [10, 30]

기능은 정상적으로 작동하지만 우리의 목표는 작동하는 기능이 아닌

더 효율적이고 효과적인 것을 찾아내는 것임을 잊어서는 안된다고 생각합니다!

 

4. 베니의 생각

와... 이 글 하나 쓰는데 며칠이 걸렸는지 모르겠습니다... ㅎㅎ..
다시 한 번 개발블로그 하시는 모든 분들 존경하며 사실 쪼개서 쓸 수도 있는 내용들인데
제 머릿 속에서 정리를 하고 작성한 것이 아닌 배우면서 바로바로 작성한 글이라 좀 더 보기 쉽게 작성하지 못한 것 같습니다.
다음 글부터는 정리를 먼저 하고 쓰는 습관을 들여야 겠습니다!

이번에 LinkedList를 글로 한 번 더 정리하면서 기억에 좀 더 남게되며 예전에 Iterator는 복잡해 보여서 그냥
공부할 때 넘어갔었었는데 정리하면서 보니 이해하는데 도움이 된 것 같습니다.
복잡해보이는 것도 끈기 있게 반복하니 이해가 된다는 좋은 경험을 했습니다.

글을 쓸 때마다 느끼는게 많고 성장을 한다는게 조금씩 느껴지네요 ㅎㅎ
다음 글은 Array List와 Linked List를 비교해보는 글을 작성하도록 하겠습니다!

TODO
- 배열 리스트( Array List )와 연결 리스트( Linked List )의 비교
댓글
댓글쓰기 폼
공지사항
최근에 달린 댓글
Total
377
Today
0
Yesterday
0
링크
«   2020/08   »
            1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25 26 27 28 29
30 31          
글 보관함