[Java][자료구조]LinkedList구현해보기

생활코딩 자료구조를 개인 공부 후 자료를 남기기 위한 목적이기에 내용 상에 오류가 있을 수 있습니다.

---

목표

• LinkedList기본메소드 구현해보기
• ListIterator 구현하여 LinkedList에 다음 객체 반복문 실행하기
• LinkedList와 ListIterator를 구현하는 LinkedList 클래스, 직접 제작한 LinkedList 클래스를 테스트 해볼 Main 클래스로 구성하여 실습

 

목차

1. LinkedList클래스

2. Main 클래스(구현한 LinkedList클래스 테스트)

3. Main 클래스 실행 결과

 

 

1. LinkedList클래스

package list.linkedlist.implementation;

public class LinkedList {

	/* ArrayList 구현해보기 */
	// 공부 홈페이지 https://opentutorials.org/module/1335/8857	
	
	/* LinkedList 객체 구현 */
	// 제일 첫 노드
	private Node head;
	// 제일 마지막 노드
	private Node tail;
	// LinkedList 크기(노드 갯수)
	private int size = 0;
	// 객치지향 프로그래밍 언어에선 노드가 객체로 구현 
	// 따라서 class로 구현
	private class Node{
		// 노드에 저장되는 데이터(Data field)
		private Object data;
		// 다음 노드(Link field)
		private Node next;
		// 값을 가지는 생성자 
		public Node(Object input) {
			// 넣는 값
			this.data = input;
			// 아직 다음에 어떤노드가 올지 모르기 때문에 null
			this.next = null;
		}
		// 노드를 생성했을 때 해당 노드 데이터를 확인하기 위해서
		// toString 구현
		public String toString() {
			return String.valueOf(this.data);
		}
	}
	
	
	/* addFirst구현 */
	public void addFirst(Object input) {
		// 새로운 노드 생성(Object매개변수를 가진 생성자 사용)
		Node newNode = new Node(input);
		// 기존 head 노드가 
		//새로운 head 노드.next
		newNode.next = head;
		// 새로 생성한 노드가 head 노드
		head = newNode;
		// 노드 갯수 증가 => 크기 증가
		size++;
		//head.next가 null 이라는 것은 아직 노드가 한개도 없는경우
		// 첫노드를 생성했기때문에 첫노드는 head이자 tail
		if(head.next == null) {
			tail = head;
		}
	}
	
	/* addLast구현 */
	public void addLast(Object input) {
		Node newNode = new Node(input);
		// size가 0이라는 것은 노드가 아무것도 없는 것을 의미
		// 노드가 없을시 addFirst()를 사용하도록 설계
		// (if를통해서 addFirst를 굳이 사용한 이유는
		// 노드가 아무것도 없는상태에서는 tail또한 null인데
		// tail.next호출하면 에러가 날 수 있음)
		if(size == 0) {
			addFirst(input);
		} else {
			// 기존 마지막 노드.next에 새로운 노드를 저장
			tail.next = newNode;
			// tail을 새로운 마지막 노드를 저장
			tail = newNode;
			// 노드의 갯수 증가 => 크기 증가
			size++;
		}
	}
	
	/* node를 리턴하는 메서드 구현 */
	// 리턴값 자체가 노드이기 때문에 외부에 노출하면 안됩니다.
	// 따라서 public을 사용하지 않았습니다.
	Node node(int index) {
		Node x = head;
		for(int i=0; i<index; i++) {
			x=x.next;
		}
		return x;
	}
	
	
	
	/* add구현 */
	public void add(int k, Object input) {
		// k가 0이라는 말은 제일 첫번째 노드를 추가 한다는 의미기 때문에 addFirst사용
		if(k == 0) {
			addFirst(input);
		} else {
			// temp1 새로추가될 노드의 앞에 있을 노드
			Node temp1 = node(k-1);
			// temp2 새로추가될 노드의 뒤에 있을 노드
			Node temp2 = temp1.next;
			// 새로운 노드 newNode생성
			Node newNode = new Node(input);
			// temp1.next는 기존 temp2였지만 newNode로 변경
			temp1.next = newNode;
			// newNode.next가 temp2를 가리키도록 저장
			newNode.next = temp2;
			// 크기증가
			size++;
			//newNode.next == null이라는 말은
			//새로 생성된 노드기 제일 마지막 노드라는 의미이기때문에
			// tail을 새로 생성된 newNode로 저장 
			if(newNode.next == null) {
				tail = newNode;
			}
		}
	}
	
	
	/* 출력 구현 */
	public String toString() {
		//head 가 null이라는 것은 노드가 아무것도 없다는 것을 의미
		if(head == null) {
			return "[]";
		} 
		//head를 temp에 저장
		Node temp = head;
		String str = "[";
		//temp.next가 null일경우 반복 멈춤
		while(temp.next != null) {
			// 현재의 노드 스트링에 출력
			str += temp.data + ",";
			// 다음의 노드가 현재의 노드가 되도록 저장
			temp = temp.next;
		}
		//제일 마지막 노드의 데이터는 출력되지 않았기 때문에 출력되도록 추가
		str += temp.data;
		
		return str+"]";
	}
	
	
	/* 삭제 구현 */
	/* 첫 노드 삭제 */
	public Object removeFirst() {
		// 참조변수 temp에 head를 저장
		Node temp = head;
		// head.next를 통해서 두번째 노드를 head에 저장
		head = head.next;
		// 삭제 될 데이터 Object타입 returnData참조변수에 저장
		Object returnData = temp.data;
		// temp 비움(첫노듯 삭제)
		temp = null;
		// 한개의 노드가 줄엇음으로 크기도 줄임
		size--;
		// 삭제된 데이터 반환
		return returnData;
	}
	
	
	/* 특정 위치 노드 삭제 */
	public Object remove(int k) {
		if(k == 0) {
			return removeFirst();
		}
		Node temp = node(k-1);
		Node todoDeleted = temp.next;
		temp.next = temp.next.next;
		Object returnData = todoDeleted.data;
		if(todoDeleted == tail) {
			tail = temp;
		}
		todoDeleted = null;
		size--;
		return returnData;
	}
	
	/* 마지막 위치 노드 삭제 */
	public Object removeLast() {
		return remove(size-1);
	}
	
	
	/* size 리턴 */
	public int size() {
		return size;
	}
	
	/* 특정 순서의 노드 데이터 리턴 */
	public Object get(int k) {
		Node temp = node(k);
		return temp.data;
	}
	
	
	/* 데이터 검색 */
	public int indexOf(Object data) {
		Node temp = head;
		int index = 0;
		
		while(temp.data != data) {
			temp = temp.next;
			index++;
			if(temp == null) {
				return -1;
			}
		}
		return index;
	}
	
	
	/* ListIterator 구현 */
	
	// ListerIterator 클래스 리턴
	public ListIterator listIterator() {
		return new ListIterator();
	}
	
	// ListIterator 클래스 구현
	public class ListIterator {
		// 다음 노드를 가리키는 변수
		private Node next;
		// 다음 노드를 가기 전의 노드를 가리키는 변수
		private Node lastReturned;
		// 노드를 옮겨감에따라 현재의 위치를 저장하는 변수
		private int nextIndex;
		
		//ListIterator 생성자
		// 제일 첫 노등 head가 next변수에 저장
		ListIterator(){
			next=head;
		}
		
		/* next메소드 */ 
		// 현재의 node 데이터를 반환하고 next 변수에 다음 노드를 저장시킵니다.
		public Object next() {
			// next는 지금 현재 노드 
			// 다음 노드로 옮기기 전 현재의노드를 lastReturned 변수에 저장
			lastReturned = next;
			// 다음 노드를 next 변수에 저장
			next = next.next;
			// 노드가 이동하였기때문에 위치 nextIndex변수도 증가
			nextIndex++;
			// 노드를 옮기기전의 노드의 데이터 값을 반환
			return lastReturned.data;
		}
		
		
		/* hasNext구현 */
		public boolean hasNext() {
			//nextIndex가 size보다 작으면 true를 반환
			return nextIndex < size();
		}
		
		/* add구현 */
		public void add(Object input) {
			Node newNode = new Node(input);
			// 아직 next()메소드를 한번도 진행하지 않은경우
			// 제일 첫노드를 추가하기위해
			if(lastReturned == null) {
				// 새로운 노드를 head변수에 저장
				head = newNode;
				// 현재의 next변수를 새로운노드의next에 저장
				newNode.next = next;
			} else {
				//첫번째 노드가 아닌경우
				// 지금 현재 가리키고있는 노드의 next에 newNode(새로운노드)를 저장
				lastReturned.next = newNode;
				// 새로운 노드의 next에 현재의 next변수를 저장
				newNode.next = next;
			}
			// 현재가리키고 있는 노드를 새로운 노드로 변경
			lastReturned = newNode;
			// nextIndex증가(현재의 위치 주소)
			nextIndex++;
			//노드의 갯수가 증가하였기때문에 size변수도 증가
			size++;
		}
		
		
		/* remove 구현 */
		public void remove() {
			// remove는 현재의 노드(lastReturned)를 삭제하는 것인데 
			// next()를 한번도 사용하지 않았따면 lastReturned는 null
			// 따라서 if문을 통해 해당상황시 에러를 발생시킴
			if(nextIndex == 0) {
				throw new IllegalStateException();
			}
			// nextIndex는 다음 노드의 Index입니다.
			// 목표는 현재의 노드(lastReturned)를 삭제하는 것이기때문에
			// 현재노드의 Index(nextIndex-1)을 해줍니다.
			LinkedList.this.remove(nextIndex-1);
			//한개의 노드가 삭제되었기때문에 주소도 한칸씩 앞당겨집니다.
			nextIndex--;
		}
		
		
	}
	
}

 

2. Main 클래스

package list.linkedlist.implementation;

public class Main {

	public static void main(String[] args) {
		
		//구현한 LinkedList클래스 인스턴스화 후 참조변수 numbers에 저장
		LinkedList numbers = new LinkedList();
		System.out.println("생성 직후 출력");
		System.out.println(numbers);
		System.out.println();
		
		// 제일 앞 노드 추가
		System.out.println("*addFirst사용");
		System.out.println("추가전 : " + numbers);
		System.out.println("첫 노드에 30, 20, 10 순으로 추가");
		numbers.addFirst(30);
		numbers.addFirst(20);
		numbers.addFirst(10);
		System.out.println("추가 후 : " + numbers);
		System.out.println();
		
		
		// 제일 뒤 노드 추가
		System.out.println("*addLast사용");
		System.out.println("추가전 : " + numbers);
		System.out.println("마지막 노드에 40, 50, 60 순으로 추가");
		numbers.addLast(40);
		numbers.addLast(50);
		numbers.addLast(60);
		// node(int index)메서드가 public일 경우 사용가능한 명령문
		//System.out.println(numbers.node(3));
		System.out.println("추가 후 : " + numbers);
		System.out.println();
		
		
		// 중간에 노드 추가
		System.out.println("*add(순서,데이터)사용");
		System.out.println("추가 전" + numbers);
		System.out.println("index는 1, 데이터는 15 노드 추가");
		numbers.add(1, 15);
		System.out.println("추가 후 : " + numbers);
		System.out.println();
		
		
		// 첫 노드 삭제
		System.out.println("*removeFirst()사용");
		System.out.println("삭제 전 : " + numbers);
		System.out.println("첫 노드 삭제");
		numbers.removeFirst();
		System.out.println("삭제 후 : " + numbers);
		System.out.println();
		
		
		// 특정 위치 노드 삭제
		System.out.println("*remove(index)사용");
		System.out.println("삭제 전 : " + numbers);
		System.out.println("index 3 노드 삭제");
		numbers.remove(3);
		System.out.println("삭제 후 : " + numbers);
		System.out.println();
		
		
		// 마지막 노드 삭제
		System.out.println("*removeLast()사용");
		System.out.println("삭제 전 : " + numbers);
		System.out.println("마지막 노드 삭제");
		numbers.removeLast();
		System.out.println("삭제 후 : " + numbers);
		System.out.println();
		
		
		//LinkedList 크기 
		System.out.println("*size()사용");
		System.out.println("현재의 LinkedList 객체 : " + numbers);
		System.out.println("현재 LinkedList 객체 크기는 " + numbers.size());
		
		// 특정 순서 노드의 데이터 가져오기
		System.out.println("*get(index)");
		System.out.println("현재의 LinkedList 객체 : " + numbers);
		System.out.println("index가 3인 노드(순서 4번째 노드)의 데이터 가져오기");
		System.out.println("index가 3인 노드(순서 4번째 노드) : " + numbers.get(3));
		System.out.println();
		
		// 데이터 검색(존재시 해당 index 반환 / 존재하지 않을시 -1 반환)
		System.out.println("*indexOf(검색데이터)");
		System.out.println("현재의 LinkedList 객체 : " + numbers);
		System.out.println("데이터 30(존재하는 데이터) 검색 ");
		System.out.println("검색결과 : " + numbers.indexOf(30));
		System.out.println("데이터 80(존재하지 않는 데이터) 검색 ");
		System.out.println("검색결과 : " + numbers.indexOf(80));
		System.out.println();
		
		
		/* ListIterator 구현 */
		System.out.println("**ListIterator 구현");
		// 현재의 LinkedList를 ListIterator 타입으로 반환하여
		// 참조변수 i 에 저장
		LinkedList.ListIterator i = numbers.listIterator();
		
		// add() 구현 테스트
		System.out.println("next()메소드 사용");
		System.out.println("i.next() : " + i.next());
		System.out.println("i.next() : " + i.next());
		System.out.println("i.next() : " + i.next());
		System.out.println();
		
		/* hasNext()구현 테스트 */
		//hasNext()테스트 위해 새로운 ListIterator 생성후 사용(i2)
		LinkedList.ListIterator i2 = numbers.listIterator();
		System.out.println("*hasNext()사용한 반복문");
		while(i2.hasNext()) {
			System.out.println(i2.next());
		}
		System.out.println("실제 LinkedList : " + numbers);
		System.out.println();
		
		
		/* add()구현테스트 */
		// add()테스트를 위해 새로운 ListIterator 생성 후 사용(i3)
		LinkedList.ListIterator i3 = numbers.listIterator();
		System.out.println("*add()사용(ListIterator의 add메소드)");
		System.out.println("add() 사용하기전 현재 ListLinked : " + numbers);
		System.out.println("첫번째 노드와 세번째노드에 각각 10, 19 데이터를 가진 노드 추가");
		i3.add(10);
		i3.next();
		i3.add(19);
		System.out.println("추가후의 LinkedList : " + numbers);
		System.out.println();
		System.out.println(numbers);
		
		/* remove()구현 테스트 */
		// remove()테스트를 위해 새로운 ListIterator 생성 후 사용
		LinkedList.ListIterator i4 = numbers.listIterator();
		System.out.println("*remove()사용(ListIterator의 remove메소드)");
		System.out.println("remove를 사용하기전의 LinkedList : " + numbers); 
		System.out.println("세번째 노드(19) 삭제");
		for(int k=0;k<2;k++){
			i4.next();
		}
		i4.remove();
		System.out.println("remove를 사용 후의 LinkedList : " + numbers);
		
	}

}

 

3. Main 클래스 실행결과

* 10,20,30,40 데이터 집어넣기
[ 10,20,30,40 ]

* index1에 15값 넣기
기존 numbers 객체 : [ 10,20,30,40 ]
추가 이후 numbers 객체 : [ 10,15,20,30,40 ]

* 첫 요소(index0)에 15값 넣기
기존 numbers 객체 : [ 10,15,20,30,40 ]
추가 후 number 객체 : [ 1,10,15,20,30,40 ]

* index 3의 데이터 삭제
기존 numbers 객체 : [ 1,10,15,20,30,40 ]
적용 후 number 객체 : [ 1,10,15,30,40 ]

* 맨 앞의 요소(index 0) 데이터 삭제
기존 numbers 객체 : [ 1,10,15,30,40 ]
적용 후 number 객체 : [ 10,15,30,40 ]

* 마지막 요소 데이터 삭제
기존 numbers 객체 : [ 10,15,30,40 ]
적용 후 number 객체 : [ 10,15,30 ]

* index 1의 데이터 가져오기
numbers 객체 : [ 10,15,30 ]
index1 데이터 : 15

* 현재 size(크가, 길이) 가져오기
numbers 객체 : [ 10,15,30 ]
 size : 3

* 데이터 15 검색
numbers 객체 : [ 10,15,30 ]
 15 데이터 index(-1일 경우 값 없음) : 1
------------------------------------
* 데이터 60 검색
numbers 객체 : [ 10,15,30 ]
 60 데이터 index(-1일 경우 값 없음) : -1

* for을 통한 반복
numbers 객체 : [ 10,15,30 ]
index0 : 10
index1 : 15
index2 : 30

* Iterator을 통한 반복
numbers 객체 : [ 10,20,30,40,50 ]
10
20
30
40
50

* 요소중 30데이터 다음 요소에 35데이터를 추가
numbers 객체 : [ 10,20,30,40,50 ]
변경 후 numbers 객체 : [ 10,20,30,35,40,50 ]
* 요소중 30데이터 삭제
numbers 객체 : [ 10,20,30,40,50 ]
변경 후 numbers 객체 : [ 10,20,40,50 ] 생성 직후 출력
[]

*addFirst사용
추가전 : []
첫 노드에 30, 20, 10 순으로 추가
추가 후 : [10,20,30]

*addLast사용
추가전 : [10,20,30]
마지막 노드에 40, 50, 60 순으로 추가
추가 후 : [10,20,30,40,50,60]

*add(순서,데이터)사용
추가 전[10,20,30,40,50,60]
index는 1, 데이터는 15 노드 추가
추가 후 : [10,15,20,30,40,50,60]

*removeFirst()사용
삭제 전 : [10,15,20,30,40,50,60]
첫 노드 삭제
삭제 후 : [15,20,30,40,50,60]

*remove(index)사용
삭제 전 : [15,20,30,40,50,60]
index 3 노드 삭제
삭제 후 : [15,20,30,50,60]

*removeLast()사용
삭제 전 : [15,20,30,50,60]
마지막 노드 삭제
삭제 후 : [15,20,30,50]

*size()사용
현재의 LinkedList 객체 : [15,20,30,50]
현재 LinkedList 객체 크기는 4
*get(index)
현재의 LinkedList 객체 : [15,20,30,50]
index가 3인 노드(순서 4번째 노드)의 데이터 가져오기
index가 3인 노드(순서 4번째 노드) : 50

*indexOf(검색데이터)
현재의 LinkedList 객체 : [15,20,30,50]
데이터 30(존재하는 데이터) 검색 
검색결과 : 2
데이터 80(존재하지 않는 데이터) 검색 
검색결과 : -1

**ListIterator 구현
next()메소드 사용
i.next() : 15
i.next() : 20
i.next() : 30

*hasNext()사용한 반복문
15
20
30
50
실제 LinkedList : [15,20,30,50]

*add()사용(ListIterator의 add메소드)
add() 사용하기전 현재 ListLinked : [15,20,30,50]
첫번째 노드와 세번째노드에 각각 10, 19 데이터를 가진 노드 추가
추가후의 LinkedList : [10,15,19,20,30,50]

[10,15,19,20,30,50]
*remove()사용(ListIterator의 remove메소드)
remove를 사용하기전의 LinkedList : [10,15,19,20,30,50]
세번째 노드(19) 삭제
remove를 사용 후의 LinkedList : [10,19,20,30,50]

 

Reference

• https://opentutorials.org/module/1335/8857

 

 

Date

• 2020.05.13 작성