数据结构(3)：单链表与双链表

单链表与双链表知识点

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

链表在插入的时候可以达到O(1)的复杂度，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间。它根据灵活的内存进行动态管理。

链表的类型：单向链表，双向链表以及循环链表（循环单链表、双向循环链表）。

1、单链表

代码实现：

public class LinkedListDemo { //定义头结点 private Node first; //定义单链表中实际的数据的数目 private int items; public LinkedListDemo(){ this.first = null; this.items = 0; } //添加头结点 public void addFirst(int data){ Node node = new Node(data); node.next = first; first = node; items++; } //删除头结点 public boolean delFirst(){ if (isEmpty()){ System.out.println("链表为空。"); return false; } first = first.next; items--; return true; } //有序链表的插入，这样简单排序就可以用链表来实现，复杂度为O(N) public void add(int data){ Node newNode = new Node(data); Node previous = null; Node current = first; //按从小到大的顺序排序 while (current!=null&&data > current.data){ previous = current; current = current.next; } if (previous==null){ first = newNode; }else{ previous.next = newNode; } newNode.next = current; items++; } //查询某个特定值的节点 public Node findNode(int data){ Node current = first; while (current!=null&&current.data!=data){ if (current.next == null){ System.out.println("该节点不存在。"); return null; } current = current.next; } return current; } //删除某个特定值的节点,并返回该节点 public Node deleteNode(int data){ Node previous = null; Node current = first;//定义被删除的节点 while (current!=null&&current.data!=data){ if (current.next == null){ System.out.println("该节点不存在。"); return null; } previous = current; current = current.next; } if (previous==null){ first = first.next; }else{ previous.next = current.next; } items--; return current; } //遍历链表 public void ergodic(){ Node currentNode = first; if (currentNode==null){ System.out.println("链表为空。"); return; } while(currentNode!=null){ System.out.println(currentNode.data); currentNode = currentNode.next; } } //链表的长度 public int size(){ return items; } //判断链表是否为空 public boolean isEmpty(){ return first == null; // return items == 0; } } class Node{ public Node next; public int data; public Node(int data) { this.data = data; } }

2、双链表

每个数据结点中都有两个指针，分别指向直接后继和直接前驱。

代码实现：

public class DoubleLinkedListDemo { private OtherNode firstNode; private OtherNode lastNode; private int size; public DoubleLinkedListDemo(){ firstNode = null; lastNode = null; size = 0; } //添加头节点 public void addFirst(int data){ OtherNode newNode = new OtherNode(data); if (isEmpty()){ lastNode = newNode; }else{ firstNode.previous = newNode; newNode.next = firstNode; } firstNode = newNode; size++; } //添加尾节点 public void addLast(int data){ OtherNode newNode = new OtherNode(data); if (isEmpty()){ firstNode = newNode; }else{ lastNode.next = newNode; newNode.previous = lastNode; } lastNode = newNode; size++; } //删除头结点,并返回头结点 public OtherNode delFirst(){ if (isEmpty()){ System.out.println("链表为空。"); return null; } OtherNode current = firstNode; if (size == 1){ lastNode = null; }else { firstNode.next.previous = null; } firstNode = firstNode.next; size--; return current; } //删除尾节点，并返回尾节点 public OtherNode delLast(){ if (isEmpty()){ System.out.println("链表为空。"); return null; } OtherNode current = lastNode; if (size == 1){ firstNode = null; }else { lastNode.previous.next = null; } lastNode = lastNode.previous; size--; return current; } //将节点插入到指定值为key的节点后面 public void insertNode(int key , int data){ OtherNode newNode = new OtherNode(data); OtherNode current = firstNode; if (isEmpty()){ System.out.println("没有" + data + "的值。"); return; } while (current.data !=data){ if (current==null){ System.out.println("没有" + data + "的值。"); return; } current = current.next; } current.next.previous = newNode; newNode.next = current.next; current.next = newNode; newNode.previous = current; size++; } //删除特定的节点,并返回该节点 public OtherNode delNode(int data){ if (isEmpty()){ System.out.println("没有" + data + "的值。"); } OtherNode current = firstNode; while (current.data!=data){ if (current.next == null){ System.out.println("没有" + data + "的值。"); } current = current.next; } if (current == firstNode){ delFirst(); }else if(current == lastNode){ delLast(); }else{ current.previous.next = current.next; current.next.previous = current.previous; } size--; return current; } //正向遍历链表 public void ergodicForward(){ OtherNode current = firstNode; while (current!=null){ System.out.println(current.data); current = current.next; } } //反向遍历链表 public void ergodicBackward(){ OtherNode current = lastNode; while (current!=null){ System.out.println(current.data); current = current.next; } } //判断链表是否为空 public boolean isEmpty(){ return size == 0; //return firstNode==null&&lastNode==null; } //得到链表容量 public int size(){ return size; } } class OtherNode{ //指向前一个节点 public OtherNode previous; //指向后一个节点 public OtherNode next; //数据域 public int data; public OtherNode(int data) { this.data = data; } }

后续如有更优的方法，会继续补充。