【转】数据结构和算法 — 链表结构-白红宇

【转】数据结构和算法 — 链表结构

阅读量：4927 次

发布时间：2019-06-11

本文共 5557 字，大约阅读时间需要 18 分钟。

近来越来越感觉数据结构和算法的重要性，于是决定花时间整理一下数据结构，一来希望自己能够更加深刻地理解数据结构，二来也希望和大家认真分享一下自己的理解，希望能够一起学习，一起进步，开心每一天。

今天先复习一下数据结构中比较常见的链表。本文以图示方法和代码演示详细地对链表及相关演变的链表做一个详细的讲解。希望看到这边文章的各位博友能够评论一下，哪怕是发个“已读”也好，感觉这样才有讨论的学习氛围。

单链表

这是链表中结构最简单的，一个单链表的节点（Node）分为两部分，第一个部分保存或者显示节点的信息，另一个部分存储的是下一个节点的地址，最后一个节点存储的地址的部分指向的是空值。

单向链表的图示（上班也挺忙的，盗个图）

单链表只可向一个方向遍历，一般查找一个节点的时候需要从第一个节点开始访问，一直访问到需要的位置。而插入一个节点，对于单链表，我们只提供在链表头插入，只需要将当前插入的节点设置为头结点，next节点指向原头节点即可，删除一个节点，我们将该节点的前一个节点的next指向该节点的下一个节点。

单链表中插入新的节点

删除节点

代码实现：

public class SingleLinkedList {

private int size; //链表节点的个数

private Node head;

public SingleLinkedList(){

size = 0;

head = null;

}

private class Node{

private Object data; //每个节点的数据

private Node next; //每个节点指向下一个节点的连接

public Node(Object data){

this.data = data;

}

//在链表头部添加元素

public Object addHead(Object obj){

Node newhead = new Node(obj);

if(size == 0){

head = newhead;

}else{

newhead.next = head;

head = newhead;

}

size++;

return obj;

}

//在单链表头部进行删除

public Object delHead(){

Object obj = head.data;

head = head.next;

size--;

return obj;

}

//查找返回指定节点，找不到，返回Null

public Node FindNode(Object obj){

Node currnet = head;

for(int i = 0; i < size; i++){

if(obj.equals(currnet.data)){

return currnet;

}else{

currnet = currnet.next;

}

return null;

}

//删除指定元素，成功返回ture

public boolean delete(Object obj){

if(size == 0){

return false;

}

Node current = head;

Node previous = head;

while(!current.data.equals(obj)){

if(current.next == null){

return false;

}else{

previous = current;

current = current.next;

}

//如果删除的节点是第一个节点

if(current == head){

head = current.next;

size--;

}else{

//删除的节点不是第一个节点

previous.next = current.next;

size--;

}

return true;

}

//判断链表是否为空

public boolean isEmpty(){

return (size == 0);

}

//显示节点信息

public void display(){

if(size > 0){

Node node = head;

int template = size;

if(template == 1){

System.out.println("[" + node.data + "]");

return;

}

while(template > 0){

if(node.equals(head)){

System.out.print("["+node.data + "->");

}else if(node.next == null){

System.out.print(node.data + "]");

}else{

System.out.print(node.data + "]");

}

node = node.next;

template--;

}

System.out.println();

}else{//如果聊表一个节点都没有，直接打印【】

System.out.println("[]");

}

栈可以用单向链表来实现

栈中的pop()方法和push()方法，对应于链表的在头部删除元素deleteHead()以及在头部增加元素addHead()。

public class StackSingleLink {

private SingleLinkedList link;

public StackSingleLink(){

link = new SingleLinkedList();

}

//移除栈顶元素

public Object pop(){//实现栈的pop()方法，返回的是栈移除的元素

Object obj = link.delHead();

return obj;

}

//添加元素

public void push(Object obj){

link.addHead(obj);

}

//判断栈中是否为空

public boolean isEmpty(){

return link.isEmpty();

}

//打印栈中的元素

public void print(){

link.display();

}

双端链表

对于单向链表，如果想在尾部添加一个节点，那么必须从头部一直遍历到尾部，找到尾部的节点，然后在尾节点后面插入一个节点，但是这样的操作很麻烦，但是如果我们在设计链表的时候加上一个对尾节点的引用，那么会简单的很多。

双端链表的实现图示

代码实现：

public class DoublePointLinkedList {

private int size;//节点个数

private Node head;//头节点

private Node tail;//尾节点

public class Node{

private Object data;

private Node next;

public Node(Object obj){

this.data = obj;

}

public DoublePointLinkedList(){

size = 0;

head = null;

tail = null;

}

//链表头部新增节点

public void addHead(Object obj){

Node node = new Node(obj);

if(size == 0){ //判断链表是否为空

head = node;

tail = node;

size++;

}else{

node.next = head;

head = node;

size++;

}

//链表尾增加节点

public void addTail(Object obj){

Node node = new Node(obj);

if(size == 0){

head = node;

tail = node;

size++;

}else{

tail.next = node;

tail = node;

size++;

}

//删除头部节点,成功返回true,失败返回false

public boolean delHead(){

if(size == 0){

return false;

}

if(head.next == null){//表明链表中有一个节点

head = null;

tail = null;

}else{

head = head.next;

}

size--;

return true;

}

//判断是否为空

public boolean isEmpty(){

return (size == 0);

}

//获得链表的节点个数

public int getSize(){

return size;

}

//显示节点信息

public void display(){

if(size > 0){

Node node = head;

int template = size;

if(template > 0){

if(node.equals(head)){

System.out.print("[" + head.data + "->");

}else if(node.next == null){

System.out.print(tail.data + "]");

}else{

System.out.print( node.data + "->");

}

node = node.next;

template--;

}

System.out.println();

}else{//如果链表一个节点都没有,直接打印[]

System.out.println("[]");

}

队列（Queue）

队列可以用双端链表来实现。

public class Queue {

private DoublePointLinkedList list;

private Queue(){

list = new DoublePointLinkedList();

}

//向队列中插入一个对象（只能插入到尾部）

public void insert(Object obj){

list.addTail(obj);

}

//向队列中插入一个对象（只能从头部去除）

public void remove(){

list.delHead();

}

//判断队列中是否为空

public boolean isEmpty(){

return list.isEmpty();

}

//打印队列中的元素

public void print(){

list.display();

}

有序链表

前面的链表实现插入都是无序的，在有些应用中需要链表中的数据有序，这称之为有序链表。在有序链表中，数据是按照关键值有序排列的。一般在大多数需要使用有序数组的场合也可以使用有序链表。有序链表优于有序数组的地方是插入的速度（因为元素不需要移动），另外链表可以扩展到全部有效的使用内存，而数组只能局限于一个固定的大小中。

（图等周末休息的时候再补）

代码实现：

public class OrderLinkedList {

private Node head;

public class Node{

private int data;

private Node next;

public Node(int data){

this.data = data;

}

public OrderLinkedList(){

head =null;