华为彗通的一道面试题

Question

java语言
用自己的类实现双向链表,包括增加,插入,删除操作;

Answer 1

编了一个节点，不知对不对，请指教。public class Node
{
    public Node priNode = null;
    public Node nextNode = null;    public Node
    {
        priNode = this;
        nextNode = this;
    }    //在这个节点后增加一个节点
    public void addAtBack(Node node)
    {
        node.nextNode = nextNode;
        node.priNode = this;
        nextNode.priNode = node;
        this.nextNode = node;
    }    //删除这个节点的一个后续节点
    public Node void delAtBack()
    {
        Node deletedNode = this.nextNode;
        this.nextNode = node.nextNode.nextNode;
        this.nextNode.priNode = this;
        deletedNode.priNode = null;
        deletedNode.nextNode = null;
        return deletedNode;
    }
}

Answer 2

http://blog.csdn.net/woolceo/archive/2005/11/26/537416.aspx我写过.不过是北电笔试的时候.

Answer 3

楼主要的是双链表啊，woolceo(努力升仙) 的那个是单链表。其实java.util.LinkedList就是一个双链表，我仿照它写了一个简单的：public class DoubleLinkedList { // 节点类Node
private static class Node {
Object value;
Node prev = this;
Node next = this;
Node(Object v) {
value = v;
}
public String toString() {
return value.toString();
}
} private Node head = new Node(null);  // 头节点
private int size;  // 链表大小 // 以下是接口方法
public boolean addFirst(Object o) {
addAfter(new Node(o), head);
return true;
} public boolean addLast(Object o) {
addBefore(new Node(o), head);
return true;
}

public boolean add(Object o) {
return addLast(o);
}

public boolean add(int index, Object o) {
addBefore(new Node(o), getNode(index));
return true;
}

public boolean remove(int index) {
removeNode(getNode(index));
return true;
}

public boolean removeFirst() {
removeNode(head.next);
return true;
}

public boolean removeLast() {
removeNode(head.prev);
return true;
}

public Object get(int index) {
return getNode(index).value;
} public int size() {
return size;
}

public String toString() {
StringBuffer s = new StringBuffer("[");
Node node = head;
for(int i = 0; i < size; i++) {
node = node.next;
if(i > 0) s.append(", ");
s.append(node.value);
}
s.append("]");
return s.toString();
}

//以下是实现方法
private Node getNode(int index) {
if(index < 0 || index >= size) throw new IndexOutOfBoundsException();
Node node = head.next;
for(int i = 0; i < index; i++)
node = node.next;
return node;
}

private void addBefore(Node newNode, Node node) {
newNode.next = node;
newNode.prev = node.prev;
newNode.next.prev = newNode;
newNode.prev.next = newNode;
size++;
}

private void addAfter(Node newNode, Node node) {
newNode.prev = node;
newNode.next = node.next;
newNode.next.prev = newNode;
newNode.prev.next = newNode;
size++;
}

private void removeNode(Node node) {
node.prev.next = node.next;
node.next.prev = node.prev;
node.prev = null;
node.next = null;
size--;
}}有些地方还可以优化，比如查找时可以判断索引是否大于size的一半，如果是的话，就从另一头开始迭代。可以用这个类测试一下：public class Test { public static void main(String[] args) {
DoubleLinkedList dll = new DoubleLinkedList();

//添加
dll.add("张曼玉");
dll.add("钟楚红");
dll.add("刘嘉玲");
System.out.println(dll);

//添加到最前
dll.addFirst("林青霞");
System.out.println(dll);

//添加到最后，同添加
dll.addLast("梅艳芳");
System.out.println(dll);

//添加到指定位置
dll.add(4, "王祖贤");
System.out.println(dll); //移除最前的
dll.removeFirst();
System.out.println(dll);

//移除最后的
dll.removeLast();
System.out.println(dll);

//移除指定位置上的
dll.remove(2);
System.out.println(dll);

//返回指定位置上的元素
System.out.println(dll.get(1));

}
}输出：
[张曼玉, 钟楚红, 刘嘉玲]
[林青霞, 张曼玉, 钟楚红, 刘嘉玲]
[林青霞, 张曼玉, 钟楚红, 刘嘉玲, 梅艳芳]
[林青霞, 张曼玉, 钟楚红, 刘嘉玲, 王祖贤, 梅艳芳]
[张曼玉, 钟楚红, 刘嘉玲, 王祖贤, 梅艳芳]
[张曼玉, 钟楚红, 刘嘉玲, 王祖贤]
[张曼玉, 钟楚红, 王祖贤]
钟楚红

Answer 4

为什么Node类要声明为static？？？？？

Answer 5

以前都用C++里的指针实现这些操作，还真不习惯 java里引用变量的这种用法

Answer 6

chouy(chouy) ( ) 信誉：100 
你的Node不包含任何有意义的内容阿。。呵呵

Answer 7

晕，这都不会还做什么java工程师我考一个，看你们谁答得出~T1.javapackage test;import java.io.BufferedReader;
import java.io.Reader;public class T1 implements Runnable { private Reader in = null; public T1(Reader in) {
this.in = in;
} private boolean myalive = false; public boolean getMyalive() {
return myalive;
}

public boolean setMyalive(boolean value){
this.myalive=value;
return this.myalive;
} public synchronized void run() {
String line = null;
BufferedReader br = new BufferedReader(this.in);
myalive = true;
try {
while ((line = br.readLine()) != null && !line.equals("terminal")) {
System.out.println(line);
}
} catch (Exception e) {
e.printStackTrace();
}
myalive = false;
}
}Main.javapackage test;import java.io.PipedReader;
import java.io.PipedWriter;public class Main { /**
 * @param args
 */
public static void main(String[] args) {
PipedWriter pw = new PipedWriter();
PipedReader pr=null;
try {
pr = new PipedReader(pw);
} catch (Exception e) {
e.printStackTrace();
}
T1 t1 = new T1(pr);
Thread th1 = new Thread(t1);
System.out.println(th1.isAlive());
th1.start();
try {
pw.write("aa\n");
pw.flush();
Thread.sleep(2000);
System.out.println(t1.setMyalive(false));
System.out.println(th1.isAlive());
pw.write("bb\n");
pw.flush();
pw.write("terminal\n");
while(th1.isAlive()){
Thread.sleep(500);
}
pr.close();
pw.close();
} catch (Exception e) {
e.printStackTrace();
}
}
}运行后输出是什么，为什么~如果将Main.java中的Thread.sleep(2000);去掉，输出是什么，为什么？~如果将T1的getMyalive()和setMyalive加上synchronized标记，会出现什么情况~ 再运行会出现什么情况？~

Answer 8

新手认为：
输出：
false
aa
false
true
bb
去掉Thread.sleep(2000)后中间几句顺序不定；因为各语句执行时间不一定,而主线程和th1分时交替执行
如果将T1的getMyalive()和setMyalive加上synchronized标记，情况应该没什么变化；期待楼上高手指教

Answer 9

求购视频会议源代码!
用提供者请电:
[email protected]