티스토리 뷰

연결리스트

단순연결리스트 Singly Linked List


JDK 코드 리뷰 (1.8.0_65)

package java.util

class LinkedList


ADT

멤버변수

int size, Node<E> first, Node<E> last


메서드

private void linkFirst(E e) 첫번째 노드로 추가

void linkLast(E e) 마지막 노드로 추가

void linkBefore(E e, Node<E> succ) e데이터를 가지는 노드를 생성하고 succ노드 뒤에 추가

private E unlinkFirst(Node<E> f) 첫번째 노드 f를 삭제

private E unlinkLast(Node<E> l) 마지막 노드 l을 삭제

E unlink(Node<E> x) 노드 x를 삭제하고 element를 반환

public E getFirst() --> 위에 기본 메서드를 사용해서 구현하는 메서드들...

public E getLast()

public E removeFirst()

public E removeLast()

public void addFirst(E e)

public void addLast(E e)

public boolean add(E e)

public void add(int index, E element)

public E remove(int index)

Node<E> node(int index)

...


멤버변수

먼저 멤버변수를 보면 보통 연결리스트를 만들 때 첫번째 노드를 가리키는 헤드노드 하나만 만드는데 jdk의 경우에는 firtst와 last변수를 가지고 있다.

transient int size = 0;

/**
* Pointer to first node.
* Invariant: (first == null && last == null) ||
* (first.prev == null && first.item != null)
*/
transient Node<E> first;

/**
* Pointer to last node.
* Invariant: (first == null && last == null) ||
* (last.next == null && last.item != null)
*/
transient Node<E> last;

transient라는 문법은 생소한데 찾아보니 Serializable 인터페이스를 구현한 객체에서 사용되는 문법이다. transient로 변수를 선언하면 직렬화에서 제외된다고 한다. 직렬화를 통해 데이터를 전송할 때 보안이나 다양한 이유로 특정 데이터를 포함하고 싶지 않을 때 transient로 변수를 선언하는 식으로 사용한다고 한다. 실제 LinkedList는 Serializable 인터페이스를 구현하고 있다. 

public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable


LinkedList.add(E e)

public boolean add(E e) {
linkLast(e);
return true;
}
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}

기본적으로 자주 사용하는 add 연산을 보자. 매개변수로 Element 하나를 받아 linkLast(e)를 호출한다.

last와 first를 이용하여 마지막노드를 찾아 순회하는 과정없이 깔끔하게 노드를 추가한다.


LinkedList.add(int index, E element)

public void add(int index, E element) {
checkPositionIndex(index);

if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
final Node<E> pred = succ.prev;
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}

insertMiddleNode와 비슷한 연산! index가 마지막 노드이면 linkLast를 이용해서 마지막 노드를 삭제하면 된다.

index가 중간 노드라면 index번째에 있는 노드를 찾아서 삭제하면 된다.

이때에는 linkBefore라는 메서드를 호출하게 된다.

  • linkBefore(E e, Node<E> succ) : succ노드 뒤에 새 노드(데이터는 e)를 추가한다.

else문에 node(index) 라는 메서드는 index번째에 있는 노드를 찾아 반환하는 메서드이다.



직접 구현한 코드

ADT LinkedList

데이터

ListNode<T> head : 리스트의 헤드 역할을 하는 노드.


연산

boolean isEmpty() 리스트에 노드가 없는지 확인하는 연산.

void insertLastNode(ListNode<T> newNode) 리스트의 마지막에 새 노드를 삽입하는 연산.

void insertMiddleNode(T frontData, T newData) frontData를 데이터로 가지는 노드 앞에 newData를 가지는 노드를 삽입하는 연산.

void reverseList() 리스트를 역순으로 변경하는 연산.

void deleteLastNode() 마지막 노드를 삭제하는 연산.

ListNode<T> searchNode(T data) data를 데이터로 가지는 노드를 찾아 반환하는 연산.

void printList() 리스트의 노드를 순서대로 출력하는 연산.



Implementation

Main.java

import domain.ListNode;
import impl.LinkedList;

/**
* Created by dasom on 2016-10-02.
*/
public class Main {

public static void main(String[] args){
LinkedList<String> list = new LinkedList<>();
list.insertLastNode(new ListNode<>("월"));
list.insertLastNode(new ListNode<>("수"));
list.insertLastNode(new ListNode<>("목"));
list.insertLastNode(new ListNode<>("토"));
list.insertLastNode(new ListNode<>("일"));
list.printList();

list.insertMiddleNode("월", "화");
list.insertMiddleNode("목", "금");
list.printList();

list.reverseList();
list.printList();

list.deleteLastNode();
list.printList();
}
}


출력 결과

월 --> 수 --> 목 --> 토 --> 일
월 --> 화 --> 수 --> 목 --> 금 --> 토 --> 일
일 --> 토 --> 금 --> 목 --> 수 --> 화 --> 월
일 --> 토 --> 금 --> 목 --> 수 --> 화


domain.ListNode.java

package domain;

/**
* Created by dasom on 2016-10-02.
*/
public class ListNode<T> {
public T data;
public ListNode link;

public ListNode() {
this.data = null;
this.link = null;
}

public ListNode(T data) {
this.data = data;
this.link = null;
}

public ListNode(T data, ListNode link) {
this.data = data;
this.link = link;
}
}


impl.LinkedList.java

package impl;

import domain.ListNode;

/**
* Created by dasom on 2016-10-02.
*/
public class LinkedList<T> {

private ListNode<T> head;

public LinkedList(){
head = null;
}

public boolean isEmpty(){
return (head==null);
}

public void insertLastNode(ListNode<T> newNode){
if(isEmpty()){
head = newNode;
return;
}

ListNode<T> currentNode = head;
while(true){
if(currentNode.link == null){
currentNode.link = newNode;
break;
}else{
currentNode = currentNode.link;
}
}
}

public void insertMiddleNode(T frontData, T newData){
if(isEmpty()){
ListNode<T> newNode = new ListNode<T>(frontData);
head = newNode;
return;
}

ListNode<T> frontNode = searchNode(frontData);
if(frontNode != null){
ListNode<T> newNode = new ListNode<T>(newData);
newNode.link = frontNode.link;
frontNode.link = newNode;
}else{
System.out.println("Cannot find Node");
}
}

public void reverseList(){
ListNode<T> preNode = null;
ListNode<T> currentNode = null;
ListNode<T> nextNode = head;

while (nextNode != null){
preNode = currentNode;
currentNode = nextNode;
nextNode = nextNode.link;
currentNode.link = preNode;
}

head = currentNode;
}

public void deleteLastNode(){
ListNode<T> currentNode = head;
while(true){
if(currentNode.link.link == null){
currentNode.link = null;
break;
}else{
currentNode = currentNode.link;
}
}
}

private ListNode<T> searchNode(T data){
ListNode<T> resultNode = head;
while((resultNode != null)){
if(data.equals(resultNode.data)){
return resultNode;
}else{
resultNode = resultNode.link;
}
}
return null;
}

public void printList(){
ListNode<T> currentNode = head;
while(true){
if(currentNode.link == null){
System.out.print(currentNode.data);
break;
}else{
System.out.print(currentNode.data + " --> ");
currentNode = currentNode.link;
}
}

System.out.println();
}
}


댓글
댓글쓰기 폼
공지사항
Total
41,170
Today
70
Yesterday
59
링크
TAG
more
«   2018/07   »
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        
글 보관함