单链表
代码实现
package com.dy.xidian; public class LinkedTable<E> { private Node head; private Node tail; // 创建一个空的头节点,头结点中不保存任何数据 public LinkedTable() { head = new Node<E>(); head.data = null; head.next = null; tail = head; } static class Node<E> { public E data; public Node next; } private <E> boolean insertHead(E e) { Node<E> temp = new Node<>(); temp.data = e; temp.next = head.next; head.next = temp; return true; } public <E> boolean insertTail(E e) { Node<E> temp = new Node<>(); temp.data = e; temp.next = null; tail.next = temp; tail = temp; return true; } //获取指定位置的节点 private Node getNode(int i) { int j = 1; // p指向链表中的第一个节点(非head) Node p = this.head.next; if (i < 0) return null; if (i == 0) return head; while (p != null && j < i) { p = p.next; j++; } return p; } //获取指定位置的元素 public <E> E getElem(int i) { if (i <= 0) return null; Node<E> node = getNode(i); return node.data; } //在指定位置插入节点 public boolean insert(int i, E e) { if (i <= 0) return false; Node node = getNode(i - 1); Node<E> temp = new Node<>(); temp.data = e; temp.next = node.next; node.next = temp; return true; } //删除指定位置节点 public <E> boolean delete(int i) { if (i <= 0) return false; Node p = getNode(i - 1); Node<E> q = p.next; p.next = q.next; q.data = null; q.next = null; return true; } public static void main(String[] args) { LinkedTable<String> list = new LinkedTable<>(); list.insertTail(new String("hello1")); list.insertTail(new String("hello2")); list.insertTail(new String("hello3")); list.insert(2, new String("hello insert")); for (int i = 1; i < 5; i++) { System.out.println(list.getElem(i)); } System.out.println("---------------------"); list.delete(3); for (int i = 1; i < 4; i++) { System.out.println(list.getElem(i)); } } }
双链表
双链表中一个节点不仅指向他的后继节点还需指向他的前驱节点。
package com.dy.xidian; import java.util.Hashtable; public class LinkedTable<E> { private Node head; private Node tail; // 创建一个空的头节点,头结点中不保存任何数据 public LinkedTable() { head = new Node<E>(); head.data = null; head.next = null; head.prev = null; tail = head; } static class Node<E> { public E data; public Node next; public Node prev; } private <E> boolean insertHead(E e) { Node<E> temp = new Node<>(); temp.data = e; temp.next = head.next; if(head.next != null) head.next.prev = temp; temp.prev = head; head.next = temp; return true; } //链表初始化时使用来批量插入节点 public <E> boolean insertTail(E e) { Node<E> temp = new Node<>(); temp.data = e; temp.next = null; tail.next = temp; temp.prev = tail; tail = temp; return true; } // 获取指定位置的节点 private Node getNode(int i) { int j = 1; // p指向链表中的第一个节点(非head) Node p = this.head.next; if (i < 0) return null; if (i == 0) return head; while (p != null && j < i) { p = p.next; j++; } return p; } // 获取指定位置的元素 public <E> E getElem(int i) { if (i <= 0) return null; Node<E> node = getNode(i); return node.data; } // 在指定位置插入节点 public boolean insert(int i, E e) { if (i <= 0) return false; Node node = getNode(i - 1); Node<E> temp = new Node<>(); temp.data = e; temp.next = node.next; node.next.prev = temp; temp.prev = node; node.next = temp; return true; } // 删除指定位置节点 public <E> boolean delete(int i) { if (i <= 0) return false; Node node = getNode(i - 1); Node<E> q = node.next; node.next = q.next; q.next.prev = node; q.data = null; q.prev = null; q.next = null; return true; } public static void main(String[] args) { LinkedTable<String> list = new LinkedTable<>(); list.insertTail(new String("hello1")); list.insertTail(new String("hello2")); list.insertTail(new String("hello3")); list.insert(2, new String("hello insert")); for (int i = 1; i < 5; i++) { System.out.println(list.getElem(i)); } System.out.println("---------------------"); list.delete(3); for (int i = 1; i < 4; i++) { System.out.println(list.getElem(i)); } } }
循环链表与循环双链表
循环链表与单链表的区别是是将最后一个节点指向头节点，而循环双链表是将双链表与循环链表结合使用。
顺序表和链表的比较
存储规模无法估计时使用链表，查找频繁使用顺序表，插入频繁使用链表。
链表的应用
- 链表的逆置(创建一个头节点，每次从原链表中取一个节点，采用头插法的方式插入到新链表中去)
- 链表排序(使用直接插入排序算法)
- 找出两个链表的公共节点(如果两个链表有公共节点，那么这两个链表的形状看起来是个Y。如果这两个链表一样长，那么同时遍历两个链表会同时到达公共点。)
- 已知链表A和B分别为两个集合，其元素递增。编写函数求A与B的交集，并放到链表A中
- 一个长度为N的整型数组A[1...N]，给定整数X，设计一个时间复杂度不超过O(nlogn)的算法，查找出这个数据中所有两两之和等于X的整数对