LinkedList和单双链表。

java中提供了双向链表的动态数据结构 --- LinkedList，它同时也实现了List接口，可以当作普通的列表来使用。也可以自定义实现链表。

单向链表：一个节点=本节点数据+下个节点地址

给定两个有序链表的头指针head1和head2，打印两个链表的公共部分。

public class Lee {private Node head1;private Node head2;Lee(){this.head1= new Node(0);this.head2= new Node(0);}public void  insert1(int data){Node newNode = new Node(data);Node curNode = head1;while (curNode.next!=null){curNode=curNode.next;}curNode.next=newNode;}public void  insert2(int data){Node newNode = new Node(data);Node curNode = head2;while (curNode.next!=null){curNode=curNode.next;}curNode.next=newNode;}static class Node{public int value;public Node next;Node(int data){this.value=data;this.next=null;}}public void Plink(Node head1,Node head2){while (head1!=null&&head2!=null){if (head1.value<head2.value)head1=head1.next;else if (head1.value>head2.value)head2=head2.next;else{System.out.println(head1.value+" ");head1=head1.next;head2=head2.next;}}}public static void main(String[] args) {Lee lee = new Lee();lee.insert1(1);lee.insert1(3);lee.insert1(4);lee.insert2(4);lee.insert2(5);lee.insert2(6);lee.Plink(lee.head1, lee.head2);}
}

双向链表：一个节点=上个节点地址+本节点数据+下个节点地址

如：定义两个函数，实现在双向链表的头部及尾部插入节点

public class Lee {private Node head;Lee(){this.head= new Node(0);}public void  insertHead(int data){Node newNode = new Node(data);newNode.next=head;head.pre=newNode;head=newNode;}public void  insertTail(int data){Node newNode = new Node(data);Node current = head;while (current.next!=null){current=current.next;}current.next=newNode;newNode.pre=current;}public void printList(Node head) {Node current = head;// 从头到尾打印链表while (current != null) {System.out.print(current.value + " -> ");current = current.next;}System.out.println("null"); // 表示链表结尾}static class Node{public int value;public Node pre;public Node next;Node(int data){this.value=data;this.pre=null;this.next=null;}}public static void main(String[] args) {Lee lee = new Lee();lee.insertTail(2);lee.insertTail(3);lee.insertTail(4);lee.insertHead(4);lee.printList(lee.head);}
}