自己动手写单向链表_JAVA_编程开发_程序员俱乐部

也许是因为不想安于现状，也许是因为不想呆在外包公司，也也许是因为冲动，我于上周向公司递交离职申请，虽然现在还没有批下来，但我还先复习一下java的一些基础知识，以面对不久以后的面试。

当然我的主攻方向依然是：

1，海量数据的存储与海量数据的分析

2，如何构建高并发的大型网站

3，移动领域的开发

?

?

今天在看链表相关的内容，为此我自己写了一个简单的单向链表，在此分享给大家。

?

单向链表

?

是指链表中的节点中除了保存该节点的值外，还有一个属性指向下一个节点，同时对外只暴露一个头节点。如图所示：

?注意：红色的数字大小表示先后加入链表的顺序，我们可以发现最先加入的节点是会在链尾，最后加入节点就是头节点。

?

代码如下

SingleLinkedList.java

class="java">package com.cloud.java;

public class SingleLinkedList<E> {
    private Entry<E> head;
    private int size;

    public int size() {
        return size;
    }

    public void add(E e) {
        if (size == 0) {
            head = new Entry<E>(e, null);
            size++;
        } else if (size > 0 && !contains(e)) {
            head = new Entry<E>(e, head);
            size++;
        }
    }

    public boolean remove(E e) {
        if (size != 0) {
            if (e == null) {
                return false;
            }
            E obj = head.getValue();
            if (obj == e || (obj != null && obj.equals(e))) {
                if (size == 1) {
                    head = null;
                } else {
                    head = head.next();
                }
                size--;
                return true;
            }

            Entry<E> parent = head;
            Entry<E> current = head.next();
            while (current != null) {
                obj = current.getValue();
                if (obj == e || (obj != null && obj.equals(e))) {
                    parent.setNext(current.next());
                    size--;
                    return true;
                }
                parent = current;
                current = current.next();
            }
        }
        return false;
    }

    public E getFirst() {
        if (size != 0) {
            return head.getValue();
        }
        return null;
    }

    public E getLast() {
        if (size != 0) {
            Entry<E> current = head;
            E obj = null;
            while (current != null) {
                obj = current.getValue();
                current = current.next();
            }
            return obj;
        }
        return null;
    }

    public E removeFirst() {
        if (size != 0) {
            E obj = head.getValue();
            if (size == 1) {
                head = null;
            } else if (size > 1) {
                head = head.next();
            }
            size--;
            return obj;
        }
        return null;
    }

    public E removeLast() {
        if (size != 0) {
            E obj = null;;
            Entry<E> parent = null;
            Entry<E> temp = head;
            Entry<E> current = head;
            do {
                parent = temp;
                temp = current;
                obj = current.getValue();
                current = current.next();
            } while (current != null);
           if (parent != null) {
               parent.setNext(null);
               size--;
           }
            return obj;
        }
        return null;
    }

    public boolean contains(E e) {
        if (size != 0) {
            Entry<E> entry = head;
            E obj;
            do {
                obj = entry.getValue();
                if (obj == e || (obj != null && obj.equals(e))) {
                    return true;
                }
                entry = entry.next();
            } while (entry != null);
        }
        return false;
    }

    @Override
    public String toString() {
        if (size != 0) {
            StringBuffer sb = new StringBuffer();
            sb.append("[").append(head.getValue());
            Entry<E> current = head.next();
            while (current != null) {
                sb.append(", " + current.getValue().toString());
                current = current.next();
            }
            sb.append("]");
            return sb.toString();
        }
        return null;
    }

    private static class Entry<E> {
        private E value;
        private Entry<E> next;

        public E getValue() {
            return value;
        }

        public Entry<E> next() {
            return next;
        }

        public void setNext(Entry<E> e) {
            next = e;
        }

        public Entry(E value, Entry<E> next) {
            this.value = value;
            this.next = next;
        }
    }
}

?

测试类

SingleLinkedListTest.java

package com.cloud.java;

public class SingleLinkedListTest {

    public static void main(String[] args) {
        SingleLinkedList<String> sll = new SingleLinkedList<String>();
        sll.add("芝加哥09");
        sll.add("9神");
        sll.add("9神");
        sll.add("大9神");

        System.out.println(sll.toString());
        System.out.println(sll.size());
        System.out.println(sll.getLast());
        System.out.println(sll.getFirst());
        System.out.println(sll.removeFirst());
        System.out.println(sll.removeLast());
        System.out.println(sll.remove("9神"));
        System.out.println(sll.size());
    }
}

?

测试结果

[大9神, 9神, 芝加哥09]
3
芝加哥09
大9神
大9神
芝加哥09
true
0

?

?

• 
• 大小: 3.9 KB

• 查看图片附件