链表

c++代码示例

#include <list>
int main() {
	std::list<int> list;
	list.push_front(1);
	list.push_back(2);
	std::list<int>::iterator it = list.begin();
	while (it != list.end())
	{
		std::cout << *it++ << std::endl;
	}
	return 0;
}

java代码示例

import java.util.LinkedList;
import java.util.ListIterator;
public class Test {
    public static void main(String[] args) {
        LinkedList<Integer> linkedList = new LinkedList<>();
        linkedList.addFirst(1);
        linkedList.addLast(2);
        ListIterator<Integer> it = linkedList.listIterator();
        while(it.hasNext()){
            System.out.println(it.next());
        }
    }
}

底层区别

c++使用带头双向循环链表。源码中只有一个头节点变量。

java在jdk1.6之前使用带头双向循环链表，从1.7开始使用不带头双向不循环链表。

java为什么要这么设计呢？

1、  first / last有更清晰的链头、链尾概念，代码看起来更容易明白。

2、  first / last方式能节省new一个headerEntry。（实例化headerEntry是为了让后面的方法更加统一，否则会多很多header的空校验）

3、  在链头/尾进行插入/删除操作，first /last方式更加快捷。

个人理解：java这样设计效率与带头的并没有区别，但是实现上与c++有了一定的区别。