Data Structure (자료구조)

비전공자는 도전해볼 수 있고, 전공자는 쉽게 배울 수 있는 데이터 스트럭쳐 수업

Data Structure (자료구조) 비전공자는 도전해볼 수 있고, 전공자는 쉽게 배울 수 있는 데이터 스트럭쳐 수업

LinkedList - Java 구현

여기서는 Java에서 LinkedList를 구현하는 방법을 알아보겠습니다. LinkedList의 사용방법은 이미 ArrayList API 시간에 살펴봤습니다. ArrayList와 LinkedList 모두 List에 대해서 구현방법만 달리한 것입니다. 따라서 사용방법은 거의 같습니다.

전체소스 코드는 다음 링크에 있습니다. 
http://opentutorials.org/module/1335/8857#entirecode

객체생성

우선 두개의 파일을 만들겠습니다.

 LinkedList.java 

package list.linkedlist.implementation;

public class LinkedList {
}

 Main.java  

package list.linkedlist.implementation;

public class Main {
    public static void main(String[] args) {
		LinkedList numbers = new LinkedList();
	}

}

노드(버텍스) 구현

LinkedList에서 가장 중요한 것이 바로 노드의 구현입니다. 노드는 실제로 데이터가 저장되는 그릇과 같은 것이기 때문에 이것부터 구현을 시작합시다. 자바는 객체지향 언어이기 때문에 노드는 객체로 만들기 딱 좋은 대상입니다. 그리고 노드 객체는 리스트의 내부 부품이기 때문에 외부에는 노출되지 않는 것이 좋습니다. 그래서 private으로 지정했습니다. 사용자는 이 객체에 대해서 알 필요가 없습니다. 단지 값을 넣고 빼는 것으로 충분합니다.

head는 첫번째 노드를 지정하는 참조값입니다. tail은 꼬리라는 뜻이죠? 짐작하시겠지만 이것은 마지막 노드를 지정합니다. size는 노드의 크기를 의미합니다. 노드를 변경할 때마다 이 값들을 수정해야 합니다. 나중에 알게 되겠지만 tail이나 size는 마지막 노드를 찾거나 노드의 수를 셀 때 연산의 횟수를 획기적으로 줄여줍니다.

객체 Node는 내부적으로 data와 next 변수를 가지고 있습니다. data는 노드의 값이고, next는 다음 노드를 가리키는 참조값입니다.

이상의 내용을 코드화 시켜보겠습니다.

public class LinkedList {
    // 첫번째 노드를 가리키는 필드
	private Node head;
	private Node tail;
	private int size = 0;
	private class Node{
		// 데이터가 저장될 필드
		private Object data;
		// 다음 노드를 가리키는 필드
		private Node next;
		public Node(Object input) {
			this.data = input;
			this.next = null;
		}
		// 노드의 내용을 쉽게 출력해서 확인해볼 수 있는 기능
		public String toString(){
			return String.valueOf(this.data);
		}
	}
}

데이터 추가

시작에 추가

public void addFirst(Object input){
	// 노드를 생성합니다.
	Node newNode = new Node(input);
	// 새로운 노드의 다음 노드로 해드를 지정합니다.
	newNode.next = head;
	// 헤드로 새로운 노드를 지정합니다.
	head = newNode;
	size++;
	if(head.next == null){
		tail = head;
	}
}

끝에 추가

리스트의 끝에 데이터를 추가할 때는 tail을 사용합니다. tail이 없이도 구현이 가능합니다. 하지만 tail이 없다면 마지막 노드를 찾아야 할 것입니다. 리스트의 끝에 데이터를 추가하는 작업은 자주 있는 작업이고, 마지막 노드를 찾는 작업은 첫 노드부터 마지막 노드까지 순차적으로 탐색을 해야 하기 때문에 최악의 상황이라고 할 수 있습니다. 그래서 우리 수업에서는 tail을 사용합니다.

public void addLast(Object input){
	// 노드를 생성합니다.
	Node newNode = new Node(input);
	// 리스트의 노드가 없다면 첫번째 노드를 추가하는 메소드를 사용합니다.
	if(size == 0){
		addFirst(input);
	} else {
		// 마지막 노드의 다음 노드로 생성한 노드를 지정합니다.
		tail.next = newNode;
		// 마지막 노드를 갱신합니다.
		tail = newNode;
		// 엘리먼트의 개수를 1 증가 시킵니다.
		size++;
	}
}

중간에 추가

중간에 노드를 추가하는 방법에 앞서 특정 위치의 노드를 찾아내는 방법을 먼저 알아보겠습니다.

Node node(int index) {
	Node x = head;
    for (int i = 0; i < index; i++)
        x = x.next;
    return x;
}

 이제 node 메소드를 이용해서 특정 위치에 노드를 추가하는 메소드를 만들어보겠습니다.

public void add(int k, Object input){
	// 만약 k가 0이라면 첫번째 노드에 추가하는 것이기 때문에 addFirst를 사용합니다.
	if(k == 0){
		addFirst(input);
	} else {
		Node temp1 = node(k-1);
		// k 번째 노드를 temp2로 지정합니다.
		Node temp2 = temp1.next;
		// 새로운 노드를 생성합니다.
		Node newNode = new Node(input);
		// temp1의 다음 노드로 새로운 노드를 지정합니다.
		temp1.next = newNode;
		// 새로운 노드의 다음 노드로 temp2를 지정합니다.
		newNode.next = temp2;
		size++;
		// 새로운 노드의 다음 노드가 없다면 새로운 노드가 마지막 노드이기 때문에 tail로 지정합니다.
		if(newNode.next == null){
			tail = newNode;
		}
	}
}

출력

지금까지 데이터를 추가하는 방법을 알아봤습니다. 이제는 제대로 데이터가 추가 되고 있는지 확인하는 방법이 필요합니다. LinkedList의 toString 메소드를 구현해서 리스트가 제대로 만들어지고 있는지는 확인하는 코드를 작성해봅시다.

public String toString() {
	// 노드가 없다면 []를 리턴합니다.
	if(head == null){
		return "[]";
	}		
	// 탐색을 시작합니다.
	Node temp = head;
	String str = "[";
	// 다음 노드가 없을 때까지 반복문을 실행합니다.
	// 마지막 노드는 다음 노드가 없기 때문에 아래의 구문은 마지막 노드는 제외됩니다.
	while(temp.next != null){
		str += temp.data + ",";
		temp = temp.next;
	}
	// 마지막 노드를 출력결과에 포함시킵니다.
	str += temp.data;
	return str+"]";
}
LinkedList numbers = new LinkedList();
numbers.addLast(10);
numbers.addLast(20);
numbers.addLast(30);
System.out.println(numbers);
[10, 20, 30]

삭제

처음 노드 삭제

public Object removeFirst(){
	// 첫번째 노드를 temp로 지정하고 head의 값을 두번째 노드로 변경합니다.
	Node temp = head;
	head = temp.next;
	// 데이터를 삭제하기 전에 리턴할 값을 임시 변수에 담습니다. 
	Object returnData = temp.data;
	temp = null;
	size--;
	return returnData;
}
LinkedList numbers = new LinkedList();
numbers.addLast(5);
numbers.addLast(10);
numbers.addLast(20);
numbers.addLast(30);
System.out.println(numbers.removeFirst());
System.out.println(numbers);
5
[10, 20, 30]

중간의 데이터를 삭제

 

public Object remove(int k){
	if(k == 0)
		return removeFirst();
	// k-1번째 노드를 temp의 값으로 지정합니다.
	Node temp = node(k-1);
	// 삭제 노드를 todoDeleted에 기록해 둡니다. 
    // 삭제 노드를 지금 제거하면 삭제 앞 노드와 삭제 뒤 노드를 연결할 수 없습니다.  
	Node todoDeleted = temp.next;
	// 삭제 앞 노드의 다음 노드로 삭제 뒤 노드를 지정합니다.
	temp.next = temp.next.next;
	// 삭제된 데이터를 리턴하기 위해서 returnData에 데이터를 저장합니다.
	Object returnData = todoDeleted.data; 
	if(todoDeleted == tail){
		tail = temp;
	}
	// cur.next를 삭제 합니다.
	todoDeleted = null;	
	size--;
	return returnData;
}
LinkedList numbers = new LinkedList();
numbers.addLast(10);
numbers.addLast(15);
numbers.addLast(20);
numbers.addLast(30);
System.out.println(numbers.remove(1));
System.out.println(numbers);
15
[10, 20, 30]

엘리먼트의 크기

엘리먼트의 크기를 알아내는 법은 간단합니다. 내부적으로 size라는 값을 유지하고 있기 때문에 이 값을 돌려주기만 하면 됩니다.

public int size() {
    return size;
}
LinkedList numbers = new LinkedList();
numbers.addLast(10);
numbers.addLast(20);
numbers.addLast(30);
System.out.println(numbers.size());
3

엘리먼트 가져오기

public Object get(int k){
	Node temp = node(k);
	return temp.data;
}
LinkedList numbers = new LinkedList();
numbers.addLast(10);
numbers.addLast(20);
numbers.addLast(30);
System.out.println(numbers.get(0));
System.out.println(numbers.get(1));
System.out.println(numbers.get(2));
10
20
30

탐색

특정한 값을 가진 엘리먼트의 인덱스 값을 알아내는 방법을 알아봅시다. 값이 있다면 그 값이 발견되는 첫번째 인덱스 값을 리턴하고 값이 없다면 -1을 리턴 합니다.

public int indexOf(Object data){
	// 탐색 대상이 되는 노드를 temp로 지정합니다.
	Node temp = head;
	// 탐색 대상이 몇번째 엘리먼트에 있는지를 의미하는 변수로 index를 사용합니다.
	int index = 0;
	// 탐색 값과 탐색 대상의 값을 비교합니다. 
	while(temp.data != data){
		temp = temp.next;
		index++;
		// temp의 값이 null이라는 것은 더 이상 탐색 대상이 없다는 것을 의미합니다.이 때 -1을 리턴합니다.
		if(temp == null)
			return -1;
	}
	// 탐색 대상을 찾았다면 대상의 인덱스 값을 리턴합니다.
	return index;
}
LinkedList numbers = new LinkedList();
numbers.addLast(10);
numbers.addLast(20);
numbers.addLast(30);
System.out.println(numbers.indexOf(10));
System.out.println(numbers.indexOf(20));
System.out.println(numbers.indexOf(30));
0
1
2

반복

Iterator 객체 생성과 next 메소드

이제부터 반복 작업을 알아보겠습니다. 기본적인 반복작업은 아래와 같습니다.

for(int i=0; i<numbers.size(); i++){
	System.out.println(numbers.get(i));
}

위와 같은 방법으로 반복을 사용하셔도 됩니다. 하지만 linked list에서는 이것은 바람직하지 않은 방법입니다. 왜냐하면 ArrayList와 다르게 LinkedList에서 get은 효율적이지 않기 때문입니다. get을 호출할 때마다 내부적으로는 반복문이 실행됩니다. 이런 경우 Iterator를 사용하는 것이 유리합니다. Iterator는 내부적으로 반복 처리된 노드가 무엇인지에 대한 정보를 유지하기 때문입니다.

ListIterator it = numbers.listIterator();
while (it.hasNext()) {
	System.out.println(it.next());
}

LinkedList의 listIterator 메소드부터 만들겠습니다.

// 반복자를 생성해서 리턴해줍니다.
public ListIterator listIterator() {
	return new ListIterator();
}

ListIterator 객체는 아래와 같습니다.

public class ListIterator{
	private Node lastReturned;
	private Node next;
	private int nextIndex;
	
	ListIterator(){
		next = head;
		nextIndex = 0;
	}
}

다음 노드의 값을 리턴하는 next 메소드의 코드는 아래와 같습니다.

// 본 메소드를 호출하면 cursor의 참조값이 기존 cursor.next로 변경됩니다. 
public Object next() {
	lastReturned = next;
	next = next.next;
	nextIndex++;
	return lastReturned.data;
}
LinkedList numbers = new LinkedList();
numbers.addLast(10);
numbers.addLast(20);
numbers.addLast(30);
LinkedList.ListIterator li = numbers.listIterator();
System.out.println(li.next());
System.out.println(li.next());
System.out.println(li.next());
10
20
30

hasNext 

public boolean hasNext() {
	return nextIndex < size();
}
LinkedList numbers = new LinkedList();
numbers.addLast(10);
numbers.addLast(20);
numbers.addLast(30);
LinkedList.ListIterator li = numbers.listIterator();
while(li.hasNext()){
    System.out.println(li.next());
}
10
20
30

add

public void add(Object input){
	Node newNode = new Node(input);
	if(lastReturned == null){
		head= newNode;
		newNode.next = next;
	} else {
		lastReturned.next = newNode;
		newNode.next = next;
	}
	lastReturned = newNode;
	nextIndex++;
	size++;
}
LinkedList numbers = new LinkedList();
numbers.addLast(10);
numbers.addLast(30);
LinkedList.ListIterator li = numbers.listIterator();
while(li.hasNext()){
    if((int)li.next() == 10)
		li.add(20);
}
System.out.println(numbers);
[10, 20, 30]

 remove

public void remove(){
	if(nextIndex == 0){
		throw new IllegalStateException();
	}
	LinkedList.this.remove(nextIndex-1);
	nextIndex--;
}
LinkedList numbers = new LinkedList();
numbers.addLast(10);
numbers.addLast(15);
numbers.addLast(20);
numbers.addLast(30);
LinkedList.ListIterator li = numbers.listIterator();
while(li.hasNext()){
    if((int)li.next() == 15)
		li.remove();
}
System.out.println(numbers);
[10, 20, 30]

 ArrayList VS LinkedList

 전체코드

 LinkedList.java 

package list.linkedlist.implementation;

public class LinkedList {
    // 첫번째 노드를 가리키는 필드
	private Node head;
	private Node tail;
	private int size = 0;
	private class Node{
		// 데이터가 저장될 필드
		private Object data;
		// 다음 노드를 가리키는 필드
		private Node next;
		public Node(Object input) {
			this.data = input;
			this.next = null;
		}
		// 노드의 내용을 쉽게 출력해서 확인해볼 수 있는 기능
		public String toString(){
			return String.valueOf(this.data);
		}
	}
	public void addFirst(Object input){
		// 노드를 생성합니다.
		Node newNode = new Node(input);
		// 새로운 노드의 다음 노드로 해드를 지정합니다.
		newNode.next = head;
		// 헤드로 새로운 노드를 지정합니다.
		head = newNode;
		size++;
		if(head.next == null){
			tail = head;
		}
	}
	public void addLast(Object input){
		// 노드를 생성합니다.
		Node newNode = new Node(input);
		// 리스트의 노드가 없다면 첫번째 노드를 추가하는 메소드를 사용합니다.
		if(size == 0){
			addFirst(input);
		} else {
			// 마지막 노드의 다음 노드로 생성한 노드를 지정합니다.
			tail.next = newNode;
			// 마지막 노드를 갱신합니다.
			tail = newNode;
			// 엘리먼트의 개수를 1 증가 시킵니다.
			size++;
		}
	}
	Node node(int index) {
		Node x = head;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    }
	public void add(int k, Object input){
		// 만약 k가 0이라면 첫번째 노드에 추가하는 것이기 때문에 addFirst를 사용합니다.
		if(k == 0){
			addFirst(input);
		} else {
			Node temp1 = node(k-1);
			// k 번째 노드를 temp2로 지정합니다.
			Node temp2 = temp1.next;
			// 새로운 노드를 생성합니다.
			Node newNode = new Node(input);
			// temp1의 다음 노드로 새로운 노드를 지정합니다.
			temp1.next = newNode;
			// 새로운 노드의 다음 노드로 temp2를 지정합니다.
			newNode.next = temp2;
			size++;
			// 새로운 노드의 다음 노드가 없다면 새로운 노드가 마지막 노드이기 때문에 tail로 지정합니다.
			if(newNode.next == null){
				tail = newNode;
			}
		}
	}
	public String toString() {
		// 노드가 없다면 []를 리턴합니다.
		if(head == null){
			return "[]";
		}		
		// 탐색을 시작합니다.
		Node temp = head;
		String str = "[";
		// 다음 노드가 없을 때까지 반복문을 실행합니다.
		// 마지막 노드는 다음 노드가 없기 때문에 아래의 구문은 마지막 노드는 제외됩니다.
		while(temp.next != null){
			str += temp.data + ",";
			temp = temp.next;
		}
		// 마지막 노드를 출력결과에 포함시킵니다.
		str += temp.data;
		return str+"]";
	}
	public Object removeFirst(){
		// 첫번째 노드를 temp로 지정하고 head의 값을 두번째 노드로 변경합니다.
		Node temp = head;
		head = temp.next;
		// 데이터를 삭제하기 전에 리턴할 값을 임시 변수에 담습니다. 
		Object returnData = temp.data;
		temp = null;
		size--;
		return returnData;
	}
	public Object remove(int k){
		if(k == 0)
			return removeFirst();
		// k-1번째 노드를 temp의 값으로 지정합니다.
		Node temp = node(k-1);
		// 삭제 노드를 todoDeleted에 기록해 둡니다. 
        // 삭제 노드를 지금 제거하면 삭제 앞 노드와 삭제 뒤 노드를 연결할 수 없습니다.  
		Node todoDeleted = temp.next;
		// 삭제 앞 노드의 다음 노드로 삭제 뒤 노드를 지정합니다.
		temp.next = temp.next.next;
		// 삭제된 데이터를 리턴하기 위해서 returnData에 데이터를 저장합니다.
		Object returnData = todoDeleted.data; 
		if(todoDeleted == tail){
			tail = temp;
		}
		// cur.next를 삭제 합니다.
		todoDeleted = null;	
		size--;
		return returnData;
	}
	public Object removeLast(){
		return remove(size-1);
	}
	public int size(){
		return size;
	}
	public Object get(int k){
		Node temp = node(k);
		return temp.data;
	}
	public int indexOf(Object data){
		// 탐색 대상이 되는 노드를 temp로 지정합니다.
		Node temp = head;
		// 탐색 대상이 몇번째 엘리먼트에 있는지를 의미하는 변수로 index를 사용합니다.
		int index = 0;
		// 탐색 값과 탐색 대상의 값을 비교합니다. 
		while(temp.data != data){
			temp = temp.next;
			index++;
			// temp의 값이 null이라는 것은 더 이상 탐색 대상이 없다는 것을 의미합니다.이 때 -1을 리턴합니다.
			if(temp == null)
				return -1;
		}
		// 탐색 대상을 찾았다면 대상의 인덱스 값을 리턴합니다.
		return index;
	}

	// 반복자를 생성해서 리턴해줍니다.
	public ListIterator listIterator() {
		return new ListIterator();
	}
	
	class ListIterator{
		private Node lastReturned;
		private Node next;
		private int nextIndex;
		
		ListIterator(){
			next = head;
			nextIndex = 0;
		}
		
		// 본 메소드를 호출하면 next의 참조값이 기존 next.next로 변경됩니다. 
		public Object next() {
			lastReturned = next;
			next = next.next;
			nextIndex++;
			return lastReturned.data;
		}
		
		public boolean hasNext() {
			return nextIndex < size();
		}
		
		public void add(Object input){
			Node newNode = new Node(input);
			if(lastReturned == null){
				head= newNode;
				newNode.next = next;
			} else {
				lastReturned.next = newNode;
				newNode.next = next;
			}
			lastReturned = newNode;
			nextIndex++;
			size++;
		}
		
		public void remove(){
			if(nextIndex == 0){
				throw new IllegalStateException();
			}
			LinkedList.this.remove(nextIndex-1);
			nextIndex--;
		}
		
	}

}

댓글

댓글 본문
작성자
비밀번호
  1. 질문
    강의 감사히 잘 보고 있습니다.
    toString을 구현하는 6번째 동영상(출력)에서, 저는 기존의 node메소드를 활용해서 아래처럼
    코드를 짜봤는데, 우선은 Main클래스에서 실행은 잘 됩니다만, 혹시 아래처럼 했을때
    다른 부분에서 로직상의 문제가 생길 가능성이 있다거나, 또는 이고잉님의 코드보다
    메모리를 더 많이 사용하게 된다거나 하는 단점 같은 것이 있을까요?


    public String toString(){
      String str = "[ ";
      for(int i = 0; i < size-1; i++){
       str += node(i).data + ", ";
      }
      return str + tail.data + " ]";
    }
  2. 정말 잘 보고 갑니다!! 대단하십니다.
  3. 목소리 너무 꿀같고 섹시하세요. 친절하고 자세한 설명 너무나 힘이되고 감사합니다. 사랑해요!!
  4. 학생
    님같은 재능기부자들덕분에 학생들은 힘이납니다
  5. SungJin Lee
    명강의 감사합니다. 정말 많은 도움이 되었습니다.
  6. 자료구조초보
    정말 감사해요 ㅠㅠ이렇게 쉽고 이해하기 쉬운 강의 제공해주셔서
    정말 감사합니다 ㅠㅠ 여섯시간 찾아해매다가 이거듣고 한번에 이해했어요
  7. 초보자
    너무나도 친절한 설명 감사드립니다.
    덕분에 완전히 이해가 쉬웠어요~
    다음에도 좋은 강의 기다리겠습니다.
  8. 궁금합니다.
    add 메서드 부분에서 저는 강의를 보면서 이렇게 짜봣더니 문제 없이 돌아갔습니다.
    굳이 temp1, temp2로 나눠서 하신 이유가 있으신지요 제가 잘 몰라서 그런건지 ㅠㅠ

    public void add(int k, Object input) {
    if (k == 0) {
    addFirst(input);
    } else {
    Node newNode = new Node(input);
    Node temp = node(k);
    node(k-1).next = newNode;
    newNode.next = temp;
    size++;

    if (newNode.next == null) {
    tail = newNode;
    }
    }
    }
  9. 지행인
    혹시라도 빛과소금 님과 비슷한 질문을 가지고 있으신 분이 있을것 같아서 답변 드립니다.
    LinkedList 자바 이미 구현되어있는 부분을 보면, remove 메쏘드가 오브젝트를 리턴하게 되어있습니다. 개인이 구현한다면 원래의 메쏘드를 직접 구현하는 것이기 때문에 똑같이 object를 return 하는 것이라고 판단됩니다.
  10. 자료구조초보
    안녕하세요!! 항상 좋은 강의 잘 보고 배우고 갑니다. 다름이 아니라 indexOf 메소드를 실행하는 과정에서
    Node의 data값이 숫자 128 이상으로 넘어가면 찾을수 없어서 -1이 리턴되는데 하는데 이유가 왜인지 알고싶습니다 ㅠㅠ
  11. 빛과소금
    궁금한게 있는데요. head 항상 첫번째 순서의 노드를 의미하게 강제되어 있는 건가요? 그리고 삭제할 데이터를 굳이 리턴이 되게 강제하는 이유가 무엇인지 알고 싶습니다. 만약을 대비해서 저장을 하는 건지 잘 모르겠지만 그냥 삭제해도 될 상황이면 삭제해도 될 것 같다는 생각이 들어서요.
  12. 빛과소금
    항상 좋은 강의 감사드립니다. Queue, Big Oh 또는 다른 data structure 에 대한 강의 올려주실 계획 가지고 계신지 궁금하네요~
버전 관리
egoing
현재 버전
선택 버전
graphittie 자세히 보기