链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
上图中 第一行为单链表,(数据区和next指针区)
· 第二行为双链表(数据区,next指针区和last指针区)
用pre,next,head三个指针来完成对链表节点的不断记录,让链表节点的指针变换。
//定义单链表节点
public static class Node{
public int value;
public Node next;
public Node(int data){
value=data;
}
}
//单链表反转
public static Node reverseLinkedList(Node head){
Node pre=null;
Node next=null;
while (head!=null){
next=head.next;
head.next=pre;
pre=head;
head=next;
}
return pre;
}
双链表反转
双链表节点比单链表节点多了一个指向上一个节点的指针,使双链表比单链表更加灵活,但反转的思路跟单链表一样。
初始链表
进行反转的链表
//定义双链表
public static class DoubleNode{
public int value;
public DoubleNode last;
public DoubleNode next;
public DoubleNode(int data){
value=data;
}
}
//双链表反转
public static DoubleNode reverseDoubleList(DoubleNode head){
DoubleNode pre=null;
DoubleNode next=null;
while (head!=null){
next=head.next;
head.next=pre;
head.last=next;
pre=head;
head=next;
}
return pre;
}
单链表实现队列
数据结构中队列的特点为:先进先出
用链表实现,就需要有两个头尾指针变量来记录跟踪。
public class LinkedListToQueue {
//单链表实现队列结构
public static class Node{
public V value;
public Node next;
public Node(V v){
value=v;
next=null;
}
}
public static class MyQueue{
private Node head;
private Node tail;
private int size;
public MyQueue(){
head=null;
tail=null;
size=0;
}
//判断队列是否为空
public boolean isEmpty(){
return size==0;
}
//得到队列的尺寸
public int size(){
return size;
}
//进入队列
public void offer( V value){
Node cur=new Node<>(value);
if (tail==null){
head=cur;
tail=cur;
}else {
tail.next=cur;
tail=cur;
}
size++;
}
//弹出队列
public V poll(){
V ans=null;
if (head!=null){
ans=head.value;
head=head.next;
size--;
}
if (head == null){
tail=null;
}
return ans;
}
//只得到值不弹出
public V peek() {
V ans=null;
if (head!=null){
ans=head.value;
}
return ans;
}
}
}
单链表实现栈结构
栈结构的特点为:先进后出
相对于队列结构,写栈结构的思路更加简单一些,只需要不断让进栈的节点往下沉。
public class LinkedListToStack {
public static class Node{
public V value;
public Node next;
public Node(V v) {
value = v;
next = null;
}
public static class MyStack{
private Node head;
private int size;
public MyStack(){
head=null;
size=0;
}
//判断是否为空
public boolean isEmpty(){
return size==0;
}
//得到栈的长度
public int size(){
return size;
}
//推入栈顶
public void push(V value){
Node cur=new Node<>(value);
if (head!=null){
cur.next=head;
head=cur;
}else{
head=cur;
}
size++;
}
//出栈
public V pop(){
V ans=null;
if (head!=null){
ans=head.value;
head=head.next;
size--;
}
return ans;
}
//得到节点的数据
public V peek(){
return head!=null?head.value:null;
}
}
}
}



