Go语言视频零基础入门到精通

javalearner · 发表于 2014-11-19 00:10:01

java实现双向循环链表和单链表.
1.双向循环链表

public class LinkedList
{
private int size = 0;
private Node
head = new Node
(null, null, null);
public LinkedList() {
head.next = head.previous = head;
}
public void add(E date) {
//核心循环双向链表
//新节点的prev指向头结点的prev 新节点的next指向头结点
Node< E> newNode = new Node< E>(head.previous, date, head);
newNode.previous.next = newNode; //调整，新节点的前一个的后一个
newNode.next.previous = newNode; //调整，新节点的后一个的前一个
size++;
}
public E get(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("Index:" + index + ",size:" + size);
}
Node< E> node = head;
if (index < (size >> 1)) {
for (int i = 0; i<= index; i++){//head是哑元，i<=index当index=0时，返回head.next
node = node.next; //对头结点进行迭代
}
}else{
for(int i=size;i>index;i--){
node=node.previous;
}
}
return node.getData();
}
public int size() {
return size;
}
public static void main(String[] args) {
LinkedList< Integer> list = new LinkedList< Integer>();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
list.add(5);
list.add(6);
list.add(7);
list.add(8);
System.out.println("list.get(3)="+list.get(3));
for (int i = 0; i < list.size(); i++) {
System.out.println(list.get(i));
}
}
class Node< E> {
E data;
Node< E> next;
Node< E> previous;
public Node(Node< E> previous, E data, Node< E> next) {
this.data = data;
this.next = next;
this.previous = previous;
}
public E getData(){
return data;
}
public void setData(E data){
this.data=data;
}
}
}
2、单链表：
public class SingleLinkedList< T> {
private int size = 0;
private Iterator ite;//迭代器
private Node< T> head, tail;
public SingleLinkedList() {
head = tail = null;
}
public void add(T data) {
if (size == 0) {
head = tail = new Node< T>(data, null);
} else {
tail.next = new Node< T>(data, null);
tail = tail.next;
}
size++;
}
public T get(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("Index:" + index + ",size:" + size);
}
Node< T> node = head;
//当index=0时，i不小于index(零不小于零)，于是直接return头结点，与linkedList不同，head不是哑元
for (int i = 0; i < index; i++) {
node = node.next; //对头结点进行迭代
}
return node.getData();
}
public int size(){
return size;
}
public Iterator< T> iterator(){
return new SingleLinkedListIterator();
}
public static void main(String[] args){
SingleLinkedList< Integer> list=new SingleLinkedList< Integer>();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
list.add(5);
list.add(6);
for(int i=0;i< list.size();i++){
System.out.println(list.get(i));
}
System.out.println("====================================");
Iterator< Integer> it=list.iterator();
while(it.hasNext())
System.out.println(it.next());
}
class SingleLinkedListIterator implements Iterator< T>{
private Node< T> current;
public SingleLinkedListIterator(){
if(size==0) current=null;
else current=head;
}
public boolean hasNext(){
return current!=null;
}
public T next(){
if(!hasNext()) {
System.out.println("没有元素了");
return null;
}
else{
T t=current.getData();
current=current.next;
return t;
}
}
}
class Node< T> {
T data;
Node< T> next;
public Node(T data, Node< T> next) {
this.data = data;
this.next = next;
}
public T getData(){
return data;
}
public void setData(T data){
this.data=data;
}
}
interface Iterator< T>{
boolean hasNext();
T next();
}
}

复制代码

这两个链表最大的不同就是头结点是否是哑元，以及取出元素（get函数）的时候for循环变量i的不同：双向循环链表（和java.util包的设计一样）：由于head是哑元，因此取元素从head的下一个结点取单向链表：head不是哑元，第一次必须取head头结点的元素，因此循环上和双向循环链表不同。也就是第一次get并没有进入for循环，直接返回了头结点，从第二次才开始进入for循环，这里要特别注意。















源码下载：http://file.javaxxz.com/2014/11/19/001000828.zip

		自动登录	找回密码
密码			立即注册

JAVA高级面试进阶视频教程	Java架构师系统进阶VIP课程	分布式高可用全栈开发微服务教程	Go语言视频零基础入门到精通	Java架构师3期(课件+源码)
Java开发全终端实战租房项目视频教程	SpringBoot2.X入门到高级使用教程	大数据培训第六期全套视频教程	深度学习（CNN RNN GAN）算法原理	Java亿级流量电商系统视频教程
互联网架构师视频教程	年薪50万Spark2.0从入门到精通	年薪50万！人工智能学习路线教程	年薪50万！大数据从入门到精通学习路线	年薪50万！机器学习入门到精通视频教程
仿小米商城类app和小程序视频教程	深度学习数据分析基础到实战	最新黑马javaEE2.1就业课程	从 0到JVM实战高手教程	MySQL入门到精通教程

分布式高可用全栈开发微服务教程

Go语言视频零基础入门到精通

Java开发全终端实战租房项目视频教程

SpringBoot2.X入门到高级使用教程

大数据培训第六期全套视频教程

Java亿级流量电商系统视频教程

年薪50万Spark2.0从入门到精通

年薪50万！人工智能学习路线教程

[算法学习]双向循环链表和单链表(java)

相关帖子